c - 稀疏矩阵-矩阵乘法

Question

我目前正在使用稀疏矩阵，我必须将稀疏矩阵-矩阵乘法的计算时间与全矩阵-矩阵乘法进行比较。问题是稀疏矩阵计算比全矩阵计算慢得多。

我正在使用 Compressed Row Storage 压缩我的矩阵，并且将 2 个矩阵相乘非常耗时（四倍循环），所以我想知道是否有更好的压缩格式更适合矩阵矩阵运算（CRS 非常方便用矩阵向量计算）。

提前致谢！

Answer 1

它通常被称为“压缩稀疏行”（CSR），而不是 CRS。转置压缩稀疏列 (CSC) 也很常用，包括CSparse包，该包最终成为很多系统的后端，包括 MatLAB 和 SciPy（我认为）。

组合 BLAS 还使用了一种不太常见的双重压缩稀疏列 (DCSC) 格式。它再次压缩列索引，对于矩阵超稀疏的情况很有用。超稀疏矩阵的大多数列都是空的，这在 2D 矩阵分解中会发生。

也就是说，是的，还有更多的开销。但是，您的操作现在由非零的数量而不是维度主导。因此，您的 FLOPS 可能会更少，但您仍然可以更快地得到答案。

Answer 2

您可以查看使用颜色的高效稀疏矩阵矩阵产品http://www.mcs.anl.gov/papers/P5007-0813_1.pdf论文，讨论如何使用稀疏矩阵矩阵产品实现高性能。