稀疏矩阵

稀疏矩阵 (Sparse Matrix)

稀疏矩阵是数值计算与数据科学中最基础的数据结构之一。当矩阵中绝大部分元素为零时，将其按稠密方式存储和处理将造成内存与算力的极大浪费——因此，稀疏矩阵的研究围绕着"如何仅存储和操作非零元素"这一核心问题展开。

稀疏矩阵是指在所有元素中，零元素占绝大多数的矩阵。与之相对，零元素较少的矩阵称为稠密矩阵（Dense Matrix）。在科学与工程计算、图论、机器学习等领域，大规模稀疏矩阵极为常见——例如，有限元分析中的刚度矩阵每行仅有少量非零元，PageRank算法处理的网页链接矩阵包含数十亿行却平均每行只有几十个链接。

设矩阵 $A \in \mathbb{R}^{m \times n}$ 含有 $\tau$ 个非零元素。当 $\tau \ll m \times n$ 时，$A$ 即为稀疏矩阵。实践中，稀疏度通常以非零元占总元素数的比例衡量——典型的大规模稀疏问题中，该比例可能低至 $10^{-3}$ 甚至 $10^{-6}$。

存储格式

稀疏矩阵的核心优势在于节省存储空间与计算资源。由于零元素不携带信息，只需存储非零元及其位置索引即可完整表达矩阵。三种经典存储格式各有适用场景：

坐标格式（COO，Coordinate Format）。用三个数组分别记录每个非零元的行索引 $i$、列索引 $j$ 和数值 $v$。COO 结构最为直观，构造灵活，常用于从外部数据源读入稀疏矩阵的初始阶段。但 COO 不支持高效的行或列访问，通常作为中间格式使用，后续转换为 CSR 或 CSC。

压缩稀疏行格式（CSR，Compressed Sparse Row）。CSR 是矩阵向量乘法 $y = Ax$ 的首选格式，由三个数组构成：\texttt{values} 按行优先顺序存储所有非零元；\texttt{col\_indices} 记录每个非零元对应的列号；\texttt{row\_ptr} 记录每行首个非零元在 \texttt{values} 中的起始位置（长度 $m+1$），其中 $row_ptr[i+1] - row_ptr[i]$ 即为第 $i$ 行的非零元个数。CSR 的存储开销约为 $2\tau + m + 1$ 个整数加 $\tau$ 个浮点数，远小于稠密存储的 $mn$。

压缩稀疏列格式（CSC，Compressed Sparse Column）。CSC 是 CSR 的列版本，按列优先顺序存储，适用于需要高效列访问的操作（如 $A^T x$）。CSR 与 CSC 之间的转换只需对矩阵进行转置操作。

此外，对角线存储格式（DIA）适用于非零元集中在对角线附近的带状矩阵；ELLPACK 格式则用两个稠密矩阵分别存储非零元值和列索引，适合 GPU 上的向量化计算。对于模式不规则的稀疏矩阵，也可以采用混合格式或根据矩阵子区域特征自适应选择最佳格式，以兼顾内存效率与访问速度。

关键算法

稀疏矩阵的算法设计须避免对零元素的无意义操作，将计算复杂度从 $O(mn)$ 降至 $O(\tau)$。

稀疏矩阵-向量乘法（SpMV）。CSR 格式下的 SpMV 是最核心的内核：遍历 \texttt{row\_ptr} 确定每行的起止范围，对范围内每个非零元执行 $y[i] \mathrel{+}= values[k] \times x[col_indices[k]]$。其浮点运算量为 $2\tau$，内存访问量则取决于矩阵的非零元分布模式。在现代处理器上，SpMV 的性能瓶颈往往是内存带宽而非计算能力。

稀疏直接求解器。对 $Ax = b$ 进行LU 分解或Cholesky 分解时，即使 $A$ 本身高度稀疏，分解因子 $L$ 和 $U$ 可能因填入（fill-in）而变得相对稠密。填入元指分解过程中在原本为零的位置产生的新非零元。因此，稀疏直接求解法的关键步骤是对矩阵进行重排序（如最小度排序、Cuthill-McKee 算法、嵌套剖分法），以最小化填入元的数量，从而在保证数值精度的同时控制内存与时间开销。

迭代法。对于大规模稀疏线性系统，迭代法往往优于直接法。共轭梯度法（CG）适用于对称正定矩阵，GMRES 和 BiCGSTAB 适用于一般矩阵。这些方法的核心操作即为反复执行 SpMV，因此整体效率直接取决于稀疏矩阵向量乘法的实现质量。预处理技术（如不完全 LU 分解 ILU、多重网格法）可显著加速收敛。

经济学与数据科学中的应用

稀疏矩阵在经济学和计量经济学中扮演着日益重要的角色。投入产出分析中的直接消耗系数矩阵本质上是一个稀疏矩阵——每个产业仅与有限数量的上下游产业发生直接交易，其余元素均为零。大型社会网络分析中的邻接矩阵和空间计量经济学中的空间权重矩阵（反映地理相邻或经济距离关系）同样高度稀疏。此外，在文本挖掘与自然语言处理中，词-文档矩阵（term-document matrix）的每一行对应一个词、每一列对应一篇文档，由于每个词仅出现在少量文档中，该矩阵通常极为稀疏。推荐系统中的用户-物品评分矩阵也呈现类似的稀疏特征——绝大多数用户仅对少量物品进行了评分。

在计算层面，高维LASSO回归等稀疏建模方法依赖于对系数向量施加 $\ell_1$ 范数惩罚以产生稀疏解，其背后的优化问题大量使用稀疏矩阵运算。面板数据的固定效应估计中，虚拟变量设计矩阵经过组内去均值（within transformation）等预处理后亦可利用稀疏结构显著加速计算。图模型与贝叶斯网络中，精度矩阵（协方差矩阵的逆）的稀疏性对应条件独立关系，是高斯图模型估计的核心对象。在宏观经济学的动态随机一般均衡（DSGE）模型中，线性化后的大型线性系统常借助稀疏求解器完成政策函数迭代。随着大数据时代的到来和数据集维度的持续膨胀，稀疏矩阵的存储策略与高效算法已成为计算经济学和数据科学基础设施中不可或缺的组成部分。