稀疏矩阵表示与运算

形式陈述 ​

对 $A=(a_{ij})\in {\mathbb{F}}^{m\times n}$，记

$$\mathrm{nnz}(A)=\mathrm{\#}\{(i,j):a_{ij}\ne 0\}.$$

当 $\mathrm{nnz}(A)\ll mn$，逐项保存全部零元素会让存储和运算成本掩盖真实结构。稀疏表示保存数值及其索引，并把“按行访问、按列访问还是持续插入”纳入数据模型；稀疏性不是脱离操作模式的单一标签。

规范 COO 格式用三个等长数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。保存三元组

$$({\text{row}}_k,{\text{col}}_k,{\text{val}}_k),1\le k\le \mathrm{nnz}(A).$$

装配阶段常允许同一位置重复出现；此时数组长度是贡献条目数，可能大于最终的 $\mathrm{nnz}(A)$。转入规范计算格式前必须排序、合并重复项并约定是否删除显式零。CSR 格式把元素按行连续保存，以长度 $m+1$ 的 row pointer 标出每行区间，再用 column index 与 values 保存列号和数值；CSC 交换行列角色，适合按列遍历。三者在规范化后的主体存储与 $\mathrm{nnz}$ 成正比，另加行或列指针，而不是 $O(mn)$。

CSR 中的稀疏矩阵—向量乘法按行计算

$$y_i=\sum _{k={\mathrm{rowptr}}_i}^{{\mathrm{rowptr}}_{i+1}-1}{\mathrm{values}}_k{x}_{{\mathrm{colidx}}_k}.$$

它需要 $O(m+\mathrm{nnz}(A))$ 时间；当每行至少有一个非零元时常简写为 $O(\mathrm{nnz})$。顺序遍历一行很快，但查找任意 $a_{ij}$ 需要扫描该行，或在列号已排序时二分搜索，不具有稠密数组式的普遍 $O(1)$ 随机访问。

稀疏模式还可看成一张二部图公理库有限简单无向图Graph · Finite simple undirected graph · 图用有限顶点集合和无序二元边集合表示的简单无向图。：行顶点与列顶点之间的边表示结构非零；方阵若来自邻接或局部耦合，也可直接按未知量图理解。置换行列就是重编号顶点，带宽、消去顺序和并行分区因而都与图结构相连。

直觉 ​

稠密矩阵像一张完整表格，稀疏矩阵更像一份边清单。真正有信息的是“谁与谁相连”和连接权重，而大片零区域只表示没有直接耦合。选格式是在选择主要阅读方向：CSR 把一行的邻居放在一起，CSC 把一列的贡献放在一起，COO 则方便先收集再整理。

这种压缩会把某些原本简单的操作变贵。插入一个新位置可能移动连续数组，任意元素查询需要索引搜索，两个稀疏模式相乘还要动态发现输出位置。节省空间不是免费抽象，而是一组明确的访问权衡。

例子与边界 ​

在 $q\times q$ 内部网格上用五点 stencil 离散二维 Poisson 算子，共有 $N=q^2$ 个未知量。每行至多连接中心和上下左右五个位置，所以

$$\mathrm{nnz}(A)\le 5N.$$

一次 SpMV 因而是 $O(N)$，CSR 存储也是 $O(N)$；若按稠密 $N\times N$ 矩阵处理，存储与乘法分别膨胀到 $O(N^2)$。这种局部耦合正是 PDE 离散与大规模迭代法能够扩展的基础。

稀疏 $A$ 的逆通常并不稀疏。即使不显式求逆，Gaussian 消元产生的 Schur 补也会在原来为零的位置出现 fill-in；因子非零数可能远大于 $\mathrm{nnz}(A)$。重排序可以减少填充，却不能由“输入稀疏”直接推出“因子同样稀疏”。

稀疏矩阵乘积也可能变稠密。若某个中间顶点连接许多行列，$AB$ 会为大量原本无直接边的顶点对产生非零项；计算成本应按实际乘法模式和输出 $\mathrm{nnz}$ 分析，不能只把两项输入非零数相加。

结构零与数值很小的元素不同。前者由模型保证不存在耦合，后者可能携带关键物理效应或维持正定性；按固定 epsilon 删除小元素会改变问题。若需要 drop tolerance，必须把它作为近似算法及误差来源公开。

推论与应用 ​

Krylov 方法公理库Krylov 子空间Krylov subspace · Arnoldi iteration · Lanczos iteration从初始向量反复施加矩阵，生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。把矩阵主要当作 $v\mapsto Av$ 接口，CSR/CSC 的线性成本使其无需形成高次幂或稠密因子。图 Laplacian、有限差分和有限元矩阵也共享这种“局部模式加数值权重”的表示。

工程验收应报告维度、$\mathrm{nnz}$、格式、索引宽度、排序和重复项约定，并分别计量 SpMV、格式转换和因子填充。只给“稀疏率百分比”不足以预测随机访问、缓存行为、并行度或直接求解成本。

参考资料

• National Institute of Standards and Technology, Matrix Market Exchange Formats.
• Richard Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed., SIAM, 1994.
• Iain S. Duff, Albert M. Erisman, and John K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, 1986.