matlab - 访问稀疏矩阵中的元素是否有开销

Question

假设我有一个稀疏矩阵 A。我想对其进行大量计算。计算不修改 A，仅访问其元素，例如取一排 A 然后乘以某物。我想知道我是应该在做任何计算之前将 A 转换为一个完整的矩阵，还是直接做？
换句话说，访问稀疏矩阵中的元素是否比完整矩阵慢？

Answer 1

在 MATLAB 中跨列切片稀疏矩阵比跨行切片快得多。所以你应该更喜欢访问 M(:,i) 而不是 M(i,:)。

MATLAB 内部使用 Compressed Sparse Column (CSC) 存储:

• 非零元素存储在长度为 nzmax 的一维 double 组中，排列在 column-major order 中(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);

这是存储在内存中的样子(我为 ir 和 jc 使用基于 0 的索引):

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

要检索稀疏矩阵 M(:,i) 的第 i 列，只需执行以下操作:pr(jc(i):jc(i+1)- 1)(为简单起见，我没有关注基于 0 和 1 的索引)。另一方面，访问矩阵行涉及更多的计算和数组遍历(它不再是 spatial-locality 友好的)。

这里有一些指向 MATLAB 文档的链接以获取更多信息:Sparse Matrices , Manipulating Sparse Matrices

---

值得一试 original paper作者:John R. Gilbert、Cleve Moler 和 Robert Schreiber:“Matlab 中的稀疏矩阵:设计和实现”，(SIAM Journal on Matrix Analysis and Applications，13:1, 333–356 (1992)).

以下引用上述论文中的一些内容来回答您关于稀疏存储开销的问题:

The computational complexity of simple array operations should be proportional to nnz, and perhaps also depend linearly on m or n, but be independent of the product m*n. The complexity of more complicated operations involves such factors as ordering and fill-in, but an objective of a good sparse matrix algorithm should be:

The time required for a sparse matrix operation should be proportional to number of arithmetic operations on nonzero quantities.

我们称之为“时间与失败成正比”规则；它是一个 我们设计的基本原则。

和

This (column-oriented sparse matrix) scheme is not efficient for manipulating matrices on element at a time: access to a single element takes time at least proportional to the logarithm of the length of its column; inserting or removing a nonzero may require extensive data movement. However, element-by-element manipulation is rare in MATLAB (and is expensive even in full MATLAB). Its most common application would be to create a sparse matrix, but this is more efficiently done by building a list [i,j,s] of matrix elements in arbitrary order and then using sparse(i,j,s) to create the matrix.

The sparse data structure is allowed to have unused elements after the end of the last column of the matrix. Thus an algorithm that builds up a matrix one column at a time can be implemented efficiently by allocating enough space for all the expected nonzeros at the outset.

还有第 3.1.4 节“渐近复杂性分析”应该很有趣(在这里引用太长了)。