我什么时候应该使用`sparse`?

塞西莉亚

我一直在仔细阅读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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章