計算效率：稀疏與滿

Question

我發現如果一個矩陣（幾乎）滿了，那麼將其存儲在稀疏中會導致（很多）更多的時間來計算。

儘管存儲稀疏形式的完整矩陣並不重要，但我只是想知道這個事實背後的原因。

我的猜測是，稀疏的索引讀數將是計算時間的主要貢獻者。任何其他優雅的想法？

Answer 1

幾乎完全稀疏矩陣比使用完整矩陣計算更昂貴的原因有幾個。正如你指出的那樣，最明顯的是稀疏元素必須被索引（對於一般的稀疏矩陣，我相信Matlab使用了一個Compressed Row Storage方案）。

另一個不太明顯的減速是由於矢量化和流水線數據進入處理器。在完全存儲矩陣的情況下，數據處於整齊的線性格式，因此操作可以很容易地進行矢量化。對於像CRS這樣的存儲方案，情況並非如此，特別是對於矩陣*矢量運算，它往往是最常用的（例如，當使用迭代求解器來求解方程組時）。對於CRS方案，移動穿過矩陣行可以以良好的線性方式饋送到處理器，然而，從矩陣乘的向量中拉出的元素將跳過。

Answer 2

考慮以下稠密矩陣：

1 2 3 
4 5 6 
7 8 9 

如果我將其存儲在一個連續的塊：

1 2 3 4 5 6 7 8 9 

我可以直接訪問某些給定的行和列數的矩陣的元素基本算術。

現在考慮這個稀疏矩陣：

1 0 0 
0 0 2 
0 3 0 

爲了有效地存儲這個矩陣，我放棄非零元素，因此它現在成爲

1 2 3 

但是，這顯然是不足夠的信息來像矩陣向量乘法一樣進行操作！所以我們需要添加additional information來從矩陣中提取元素。

但是你可以看到存儲方法是不管用，我們需要

1. 做額外的工作訪問的元素
2. 存儲更多的信息，以保持基質的結構

正如你所看到的，只有在矩陣中有足夠的零來補償我們存儲的用於保存矩陣結構的額外信息時，存儲的好處纔會產生。例如，在Yale format中，當非零（NNZ）值的數量小於(m(n − 1) − 1)/2時，我們僅保存在內存中，其中m =行數並且n =列數。