稀疏矩陣 - 矩陣乘法

我目前正在處理稀疏矩陣，我必須比較稀疏矩陣 - 矩陣乘法和全矩陣乘法的計算時間。問題是稀疏矩陣計算比全矩陣計算慢。稀疏矩陣 - 矩陣乘法

我壓縮我的矩陣與壓縮行存儲，並乘以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你不應該因爲其他人低估而發起衝擊，如果這是發生在這裏的事情 –

回答