MATLAB稀疏性 - 在我的情况下是否有速度优势？

Question

我有一个大小为MxM的矩阵S，对角线上的元素为零，其他位置的元素都不为零。我需要制作一个更大的块状矩阵。这些块的大小将为NxN，总共会有MxM个块。

第(i,j)个块将是S(i,j)I，其中I=eye(N)是一个尺寸为NxN的单位矩阵。这个矩阵肯定是稀疏的，S有M^2-M个非零元素，我的块状矩阵将有N(M^2-M)个非零元素，占据了(NM)^2的约1/N%，但我将把它添加到另一个NMxNM的矩阵中，我不指望它是稀疏的。

由于我将把块状矩阵添加到一个全矩阵中，如果尝试以“稀疏”的方式编写代码，是否会有速度上的提升呢？我一直在反复思考，我的想法正在确定：即使将S转换为稀疏块状矩阵的代码不是很高效，当我告诉它要将一个全矩阵和一个稀疏矩阵相加时，MATLAB会知道它只需要迭代非零元素吗？ 我经常听说for循环在MATLAB中运行速度较慢，而使用repmat和用零填充则更快，但我猜最快的方法是根本不构建块状矩阵，而是编写以稀疏方式添加(小矩阵)S到我的其他(大的、全的)矩阵的代码。如果我学会了如何使用稀疏代码构建块状矩阵(比用全方式构建并传递给函数更快)，那么这段代码应该能够以稀疏的方式为我执行加法，而无需构建块状矩阵，对吗？

- Travis Bemrose

---

N和M有多大？（注意：我认为您将拥有N*(M^2-M)个非零条目，而不是M^2-M个。） - BillBokeey

如果只有对角线为零，那就不算是非常稀疏的。在这种情况下，与稀疏矩阵相关的额外开销会导致它需要更多的内存。 - IKavanagh

这个答案建议你在稀疏矩阵中分配不超过25%的空间，才能看到性能的提升。但实际上，我认为确定它是否会在你的情况下产生差异的唯一方法是实现一个最小版本的你正在运行的算法并计时。如果不知道你在矩阵上执行的确切操作，我认为我们无法提供决定性的答案。 - zelanix

正如他们在这里所说的：如果您的非零元素数量大于条目的25％，则不要使用稀疏。 - Ander Biguri

我的分块矩阵肯定会少于25%的非零条目。(即使在N=4和M=6的情况下，它也只有21%，随着规模的扩大，百分比会越来越小)。问题不在于我的分块矩阵有多稀疏。@zelanix 我要做的操作是将这个稀疏分块矩阵加到一个完整的NMxNM矩阵中。我可以处理一些玩具问题，但在我花时间学习如何编写高效的稀疏代码之前，我想知道是否有任何优势，因为这可能对我没有任何好处。 - Travis Bemrose

Answer 1

如果您可以在内存中保存完整的NMxNM矩阵，则不必使用稀疏操作。实际上，在大多数情况下，A为完整矩阵，B为稀疏矩阵的A + B所需的时间将比A和B都为完整矩阵的A + B更长。

- Felix Darvas

Answer 2

根据您的描述，对于您的问题使用稀疏矩阵可能会更慢：

如果您将稀疏矩阵A添加到全矩阵B，则结果为全矩阵，并且几乎肯定没有使A稀疏的优势。

例如： n = 12000; A = rand(n, n); B1 = rand(n, n); B2 = spalloc(n, n, n*n); B2尽可能地稀疏，也就是说，它全部都是零！ 在我的机器上，A + B1需要约0.23秒，而A + B2需要约0.7秒。

基本上，对完整矩阵的操作使用BLAS/LAPACK库调用，这些调用已经非常优化。与稀疏相关的开销会使情况变得更糟，除非您处于稀疏特别有用的特殊情况。

什么时候稀疏矩阵特别有用？

当矩阵的大小表明某些算法应该非常慢，但由于稀疏性（+可能的特殊矩阵结构），实际所需的计算量要少得多时，稀疏矩阵非常有用。

例子：解线性方程组A*x=b，其中A是块对角矩阵： As = sparse(rand(5, 5)); for(i=1:999) As = blkdiag(As, sparse(rand(5,5))); end %生成一个5000x5000的稀疏块对角矩阵，每个块为5x5

Af = full(As); b = rand(5000, 1);

在我的机器上，解决完整矩阵的线性系统（即Af \ b）需要约2.3秒，而As \ b只需要0.0012秒。

稀疏矩阵可能很棒，但只有在您可以巧妙地利用结构的大型问题中才有帮助。

- Matthew Gunn