performance - 使用稀疏矩阵时的最佳实践

Question

我的问题有两个:

在下面，A = full(S) 其中 S 是一个稀疏矩阵。

访问稀疏矩阵中元素的“正确”方法是什么？

也就是说，var = A(row, col) 的稀疏等价物是什么？

我对此主题的看法:您不会做任何不同的事情。 var = S(row, col) 尽可能高效。

向稀疏矩阵添加元素的“正确”方法是什么？

也就是说，A(row, col) = var 的稀疏等价物是什么？ (假设 A(row, col) == 0 开始)

众所周知，对于大型稀疏矩阵，简单地执行 A(row, col) = var 是很慢的。来自 the documentation :

If you wanted to change a value in this matrix, you might be tempted to use the same indexing:

B(3,1) = 42; % This code does work, however, it is slow.

我对此主题的看法:在处理稀疏矩阵时，您通常会从向量开始并使用它们以这种方式创建矩阵:S = sparse(i,j,s ,m,n)。当然，您也可以这样创建它:S = sparse(A) 或 sprand(m,n,density) 或类似内容。

如果您以第一种方式开始，您只需执行以下操作:

i = [i; new_i];
j = [j; new_j];
s = [s; new_s];
S = sparse(i,j,s,m,n); 

如果您一开始没有向量，您会做同样的事情，但使用 find第一:

[i, j, s] = find(S);
i = [i; new_i];
j = [j; new_j];
s = [s; new_s];
S = sparse(i,j,s,m,n); 

现在您当然拥有向量，并且如果您多次执行此操作，则可以重用它们。然而，最好一次添加所有新元素，而不是循环执行上述操作，因为 growing vectors are slow .在这种情况下，new_i、new_j 和new_s 将是对应于新元素的向量。

Answer 1

MATLAB 将稀疏矩阵存储在 compressed column format 中.这意味着当您执行类似 A(2,2) 的操作(获取第 2 行第 2 列的元素)时，MATLAB 首先访问第二列，然后找到第 2 行中的元素(存储每列中的行索引按升序排列)。您可以将其视为:

 A2 = A(:,2);
 A2(2)

如果您只访问稀疏矩阵的单个元素，则执行 var = S(r,c) 没问题。但是，如果您遍历稀疏矩阵的元素，您可能希望一次访问一列，然后通过 [i,~,x]=find(S(:, c))。或者使用类似 spfun 的东西。

您应该避免构建密集矩阵 A 然后执行 S = sparse(A)，因为此操作只会挤出零。相反，正如您所注意到的，使用三元组形式并调用 sparse(i,j,x,m,n) 从头开始​​构建稀疏矩阵的效率要高得多。 MATLAB 有一个 nice page其中描述了如何有效地构造稀疏矩阵。

原文paper在 MATLAB 中描述稀疏矩阵的实现是一本很好的读物。它提供了有关稀疏矩阵算法最初是如何实现的更多信息。