压缩行存储

压缩行和列（下一节介绍）存储格式是最通用的：它们对矩阵的稀疏结构不做任何假设，也不存储任何不必要的元素。另一方面，它们的效率并不高，在矩阵-向量乘积或预处理求解中，每一步标量操作都需要进行间接寻址。

压缩行存储（CRS）格式将矩阵行的后续非零元素存储在连续的内存位置中。假设我们有一个非对称的稀疏矩阵 A ，我们创建三个向量：一个用于浮点数（val），另外两个用于整数（col_ind, row_ptr）。val 向量存储矩阵 A 的非零元素的值，这些元素按行遍历。col_ind 向量存储 val 向量中元素的列索引。也就是说，如果 {\tt val(k)}=a_{i,j}，那么 {\tt col\_ind(k)}=j。row_ptr 向量存储 val 向量中每一行的起始位置；也就是说，如果 {\tt val(k)}=a_{i,j}，那么 {\tt row\_ptr(i)}\leq k<{\tt row\_ptr(i+1)}。按照惯例，我们定义 {\tt row\_ptr(n+1)} = nnz+1，其中 nnz 是矩阵 A 中非零元素的数量。这种存储方式节省了大量空间。我们不再需要存储 n^2 个元素，而只需要 2nnz+n+1 个存储位置。

举个例子，考虑由以下定义的非对称矩阵 A ：

A =\left[\begin{array}{rrrrrr} 10 & 0 & 0 & 0 & -2 & 0 \\ 3 & 9 & 0 & 0 & 0 & 0 \\ 0 & 7 & 8 & 7 & 0 & 0 \\ 3 & 0 & 8 & 7 & 5 & 0 \\ 0 & 8 & 0 & 9 & 9 & 13 \\ 0 & 4 & 0 & 0 & 2 & -1 \end{array}\right].\tag{10.1}

这个矩阵的 CRS 格式由以下数组 {val, col_ind, row_ptr} 指定：

val	10	-2	3	9	3	7	8	7	3 \cdots 9	13	4	2	-1
col_ind	1	5	1	2	6	2	3	4	1 \cdots 5	6	2	5	6

row_ptr

1

3

6

9

13

17

20

如果矩阵 A 是对称的，我们只需要存储矩阵的上三角（或下三角）部分。这样做的权衡是算法更复杂，数据访问模式也有所不同。