稀疏矩阵 - 矩阵乘法

我目前正在处理稀疏矩阵，我必须比较稀疏矩阵 - 矩阵乘法和全矩阵乘法的计算时间。问题是稀疏矩阵计算比全矩阵计算慢。稀疏矩阵 - 矩阵乘法

我压缩我的矩阵与压缩行存储，并乘以2矩阵是非常耗时（四重循环），所以我想知道是否有更好的压缩格式更适合于矩阵矩阵运算（ CRS在矩阵向量计算中非常方便）。

在此先感谢！

2013-09-26 HappyRave

请参阅：http://scicomp.stackexchange.com/questions/2226/what-is-the-overhead-in-sparse-matrix-multiplication – rerx

我不确定我是否了解您的问题，但如果您想要为了加速矩阵乘法，你可以将每个矩阵变换成对角矩阵（http://en.wikipedia.org/wiki/Diagonal_matrix），对于每个矩阵它只有O（n^3）。然后乘法仅为O（n）。 –

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

组合BLAS还有一种不太常见的双压缩稀疏列（DCSC）格式。它再次压缩列索引，并且对于矩阵过度分析的情况非常有用。超级清理矩阵的大部分列都是空的，这是2D矩阵分解时发生的情况。

这就是说，是有更多的开销。但是，您的操作现在由非标准器的数量，而不是尺寸决定。所以你的FLOPS可能会更少，但你仍然可以更快地得到你的答案。

2013-09-26 08:25:39 Adam

您可以参考有色稀疏矩阵 - 矩阵产品使用颜色http://www.mcs.anl.gov/papers/P5007-0813_1.pdf来讨论如何使用稀疏矩阵矩阵产品实现高性能。

2014-01-13 22:49:01 user1101165

由于原来的downvote，我投了票。链接的文章与该主题相关。 – shuhalo

@shuhalo你不应该因为其他人低估而发起冲击，如果这是发生在这里的事情 –

回答