稀疏矩阵表示与运算

形式陈述

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

\operatorname{nnz}(A) =\#\{(i,j):a_{ij}\ne0\}.

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

规范 COO 格式用三个等长数组保存三元组

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

装配阶段常允许同一位置重复出现；此时数组长度是贡献条目数，可能大于最终的 $\operatorname{nnz}(A)$ 。转入规范计算格式前必须排序、合并重复项并约定是否删除显式零。CSR 格式把元素按行连续保存，以长度 $m+1$ 的 row pointer 标出每行区间，再用 column index 与 values 保存列号和数值；CSC 交换行列角色，适合按列遍历。三者在规范化后的主体存储与 $\operatorname{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+\operatorname{nnz}(A))$ 时间；当每行至少有一个非零元时常简写为 $O(\operatorname{nnz})$ 。顺序遍历一行很快，但查找任意 $a_{ij}$ 需要扫描该行，或在列号已排序时二分搜索，不具有稠密数组式的普遍 $O(1)$ 随机访问。

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

直觉

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

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

例子与边界

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

\operatorname{nnz}(A)\le5N.

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

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

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

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

推论与应用

Krylov 方法把矩阵主要当作 $v\mapsto Av$ 接口，CSR/CSC 的线性成本使其无需形成高次幂或稠密因子。图 Laplacian、有限差分和有限元矩阵也共享这种“局部模式加数值权重”的表示。

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

参考资料

National Institute of Standards and Technology, Matrix Market Exchange Formats, accessed 2026.
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.

形式陈述 ​

反向链接

形式陈述