我一直在仔细阅读Matlab的sparse
文档,试图找到关于何时使用稀疏表示而不是完整表示的任何指导原则。
例如,我有一个矩阵,data
其中包含约30%的非零条目。我可以检查使用的内存。
whos data
Name Size Bytes Class Attributes
data 84143929x11 4394073488 double sparse
data = full(data);
whos data
Name Size Bytes Class Attributes
data 84143929x11 7404665752 double
在这里,我显然是在节省内存,但是对于任何包含30%非零条目的矩阵,这都是真的吗?50%的非零条目呢?我应以什么百分比切换到完整矩阵是否有经验法则?
那么计算呢?通常,用稀疏矩阵进行矩阵乘法会变慢还是变快?稀疏矩阵运算表示
稀疏运算的计算复杂度与nnz(矩阵中非零元素的数量)成正比。计算复杂度还线性地取决于矩阵的行大小m和列大小n,但与乘积m * n,零元素和非零元素的总数无关。
如果不知道更多细节,很难将其与完整矩阵进行比较。
Scipy的稀疏矩阵库说明了每种稀疏格式的优缺点。例如对于csc_matrix
CSC格式的优点
- 高效的算术运算CSC + CSC,CSC * CSC等
- 高效的列切片
- 快速矩阵向量乘积(CSR,BSR可能更快)
CSC格式的缺点
- 慢行切片操作(考虑CSR)
- 稀疏结构的更改非常昂贵(考虑LIL或DOK)
是否sparse
存在有关Matlab实现的类似信息?如果可以,我在哪里可以找到它?
在完整矩阵上的许多操作都使用BLAS / LAPACK库调用,这些调用被疯狂地优化并且难以击败。实际上,在可以充分利用(i)稀疏性和(ii)特殊矩阵结构的特殊情况下,对稀疏矩阵的操作将仅胜过对完整矩阵的操作。
只是随机使用稀疏可能会使您的情况更糟。示例:将10000x10000完整矩阵添加到10000x10000完整矩阵中哪个更快?还是将10000x10000完整矩阵添加到一个完全稀疏(即一切为零)的10000x10000矩阵中?试试吧!在我的系统上,完整+完整速度更快!
示例1:求解线性系统A * x = b,其中A为5000x5000,但它是由500个5x5块构成的块对角矩阵。设置代码:
As = sparse(rand(5, 5));
for(i=1:999)
As = blkdiag(As, sparse(rand(5,5)));
end; %As is made up of 500 5x5 blocks along diagonal
Af = full(As); b = rand(5000, 1);
然后您可以测试速度差异:
As \ b % operation on sparse As takes .0012 seconds
Af \ b % solving with full Af takes about 2.3 seconds
通常,一个5000可变的线性系统有些困难,但是1000个单独的5可变的线性系统却微不足道。后者基本上是在稀疏情况下可以解决的问题。
总的来说,如果您具有特殊的矩阵结构并且可以巧妙地利用稀疏性,则有可能解决疯狂的大问题,否则这些问题将是棘手的。如果您有一个足够大的特殊问题,具有足够稀疏的矩阵,并且对于线性代数比较聪明(以便保留稀疏性),那么稀疏类型的矩阵可能会非常有用。
另一方面,随机地将稀疏而没有深思熟虑的想法几乎肯定会使您的代码变慢。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句