MATLAB 稀疏性 - 在我的情况下有速度优势吗?
MATLAB sparsity - Is there a speed advantage in my situation?
我有一个 MxM
矩阵 S
其对角线上的元素为零,其他地方都为非零。我需要制作一个更大的块矩阵。这些块的大小为 NxN
,并且会有 MxM
个。
(i,j)th
块将是 S(i,j)I
,其中 I=eye(N)
是 NxN
身份。这个矩阵肯定是稀疏的,S
有 M^2-M
个非零条目,我的块矩阵将有 N(M^2-M)
个 (NM)^2
或大约 1/N
% 个非零条目,但是我会将它添加到另一个我不希望稀疏的 NMxNM
矩阵。
由于我将我的分块矩阵添加到一个完整矩阵中,尝试以 'sparse' 方式编写我的代码是否会提高速度? 我继续来回,但我的想法是:即使我将 S
变成稀疏块矩阵的代码不是很有效,当我告诉它把一个完整的和稀疏的矩阵加在一起时,不会' MATLAB 不知道它只需要迭代非零元素吗?我受过训练,for
循环在 MATLAB 中很慢,而像 repmat
和用零填充的东西更快,但我的猜测是最快的做法是甚至不构建块矩阵完全没有,但是编写代码以稀疏方式将(小矩阵)S
的条目添加到我的另一个(大,完整)矩阵。如果我要学习如何用稀疏代码构建块矩阵(比以完整的方式构建它并将其传递给 sparse
更快),那么该代码应该能够以稀疏的方式为我做加法甚至不需要构建块矩阵对吗?
如果你能在内存中保留一个完整的 NMxNM 矩阵,就不用为稀疏操作而烦恼了。事实上,在大多数情况下,A+B(A 满,B 稀疏)比 A+B(A 和 B 都满)花费的时间更长。
根据您的描述,对于您的问题,使用稀疏可能速度较慢:
如果您将稀疏矩阵 A 添加到完整矩阵 B,结果是完整的,几乎可以肯定 A 稀疏没有任何优势。
例如:
n = 12000; A = 随机数 (n, n); B1 = 随机数 (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 %生成一个 5x5 块的 5000x5000 稀疏块对角矩阵
Af = 满(As);
b = rand(5000, 1);
在我的机器上,求解完整矩阵(即 Af\b)上的线性系统大约需要 2.3 秒,而 As\b 需要 .0012 秒。
稀疏可能很棒,但它只对可以巧妙利用结构的大问题有帮助。
我有一个 MxM
矩阵 S
其对角线上的元素为零,其他地方都为非零。我需要制作一个更大的块矩阵。这些块的大小为 NxN
,并且会有 MxM
个。
(i,j)th
块将是 S(i,j)I
,其中 I=eye(N)
是 NxN
身份。这个矩阵肯定是稀疏的,S
有 M^2-M
个非零条目,我的块矩阵将有 N(M^2-M)
个 (NM)^2
或大约 1/N
% 个非零条目,但是我会将它添加到另一个我不希望稀疏的 NMxNM
矩阵。
由于我将我的分块矩阵添加到一个完整矩阵中,尝试以 'sparse' 方式编写我的代码是否会提高速度? 我继续来回,但我的想法是:即使我将 S
变成稀疏块矩阵的代码不是很有效,当我告诉它把一个完整的和稀疏的矩阵加在一起时,不会' MATLAB 不知道它只需要迭代非零元素吗?我受过训练,for
循环在 MATLAB 中很慢,而像 repmat
和用零填充的东西更快,但我的猜测是最快的做法是甚至不构建块矩阵完全没有,但是编写代码以稀疏方式将(小矩阵)S
的条目添加到我的另一个(大,完整)矩阵。如果我要学习如何用稀疏代码构建块矩阵(比以完整的方式构建它并将其传递给 sparse
更快),那么该代码应该能够以稀疏的方式为我做加法甚至不需要构建块矩阵对吗?
如果你能在内存中保留一个完整的 NMxNM 矩阵,就不用为稀疏操作而烦恼了。事实上,在大多数情况下,A+B(A 满,B 稀疏)比 A+B(A 和 B 都满)花费的时间更长。
根据您的描述,对于您的问题,使用稀疏可能速度较慢:
如果您将稀疏矩阵 A 添加到完整矩阵 B,结果是完整的,几乎可以肯定 A 稀疏没有任何优势。
例如: n = 12000; A = 随机数 (n, n); B1 = 随机数 (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 %生成一个 5x5 块的 5000x5000 稀疏块对角矩阵
Af = 满(As); b = rand(5000, 1);
在我的机器上,求解完整矩阵(即 Af\b)上的线性系统大约需要 2.3 秒,而 As\b 需要 .0012 秒。
稀疏可能很棒,但它只对可以巧妙利用结构的大问题有帮助。