Tu *_*Bui 2 matlab matrix overhead sparse-matrix
假设我有一个稀疏矩阵A.我想对它做大量计算.计算不修改A,只访问其元素,例如取一行A然后乘以某些东西.我想知道在进行任何计算之前是否应该将A转换为完整矩阵,还是直接进行？
换句话说,访问稀疏矩阵中的元素比完整矩阵更慢？
在列中切片稀疏矩阵比在MATLAB中切片行快得多.所以,你应该更喜欢访问M(:,i)过M(i,:).
MATLAB内部使用压缩稀疏列(CSC)存储:
nzmax以列 - 主顺序排列的长度的一维双数组中(pr对于实部和pi虚部,如果矩阵是复杂的)ir 具有相应行索引的整数数组jc包含列索引信息的整数长度数组n+1(其中n是列数).根据定义,jc包含的最后一个值nnz(存储的非零数).例如,采用以下稀疏矩阵:
>> M = sparse([1 3 5 3 4 1 5], [1 1 1 2 2 4 4], [1 7 5 3 4 2 6], 5, 4);
这就是它看起来像存储在内存中(我使用0为基础的指数ir和jc):
1 . . 2
. . . .
7 3 . .
. 4 . .
5 . . 6
pr = 1 7 5 3 4 2 6
ir = 0 2 4 2 3 0 4
jc = 0 3 5 5 7
nzmax = at least 7
nnz = 7
m = 5
n = 4
要检索稀疏矩阵的第i列,M(:,i)只需执行以下操作pr(jc(i):jc(i+1)-1):(为了保持简单,我不注意0-基于1的索引).另一方面,访问矩阵行涉及更多的计算和数组遍历(它不再是空间局部友好的).
以下是MATLAB文档的一些链接,以获取更多信息:稀疏矩阵,操作稀疏矩阵
这是值得一试的原始论文由约翰·吉尔伯特,克里夫·莫勒尔,和罗伯特·施赖伯:"稀疏矩阵在Matlab中的设计与实现",(SIAM杂志矩阵分析和应用,13:1,333-356(1992) ).
以上是上述文章中的一些引用来回答关于稀疏存储开销的问题:
简单阵列操作的计算复杂度应该与产品成比例
nnz,并且可能也线性地依赖于m或者n独立于产品m*n.更复杂的操作的复杂性涉及诸如排序和填充之类的因素,但是良好的稀疏矩阵算法的目标应该是:稀疏矩阵运算所需的时间应与非零量的算术运算次数成比例.
我们称之为"时间与翻牌成正比"的规则; 这是我们设计的基本原则.
和
这种(面向列的稀疏矩阵)方案对于一次操作元素上的矩阵是无效的:对单个元素的访问花费的时间至少与其列的长度的对数成比例; 插入或删除非零可能需要大量数据移动.但是,逐个元素的操作在MATLAB中很少见(即使在完整的MATLAB中也很昂贵).其最常见的应用是创建稀疏矩阵,但通过
[i,j,s]以任意顺序构建矩阵元素列表然后使用sparse(i,j,s)创建矩阵,可以更有效地完成此操作.允许稀疏数据结构在矩阵的最后一列结束之后具有未使用的元素.因此,通过在开始时为所有预期的非零值分配足够的空间,可以有效地实现一次建立一列矩阵的算法.
第3.1.4节"渐近复杂性分析"应该是有意义的(这里引用的时间太长).