稀疏矩阵 · aiwiki.page

稀疏矩阵是指元素大多为零，或零元素的分布使专用表示方式具有计算优势的矩阵。稠密存储会记录每一个元素，而稀疏存储通常只记录非零值及其位置信息。稀疏矩阵在数值线性代数中占有重要地位，因为这种表示方式能够显著降低内存需求，并避免涉及零元素的算术运算。稀疏性描述的是矩阵元素的特征；稀疏存储描述的则是这些元素在计算机中的表示方式。(mathworks.com)

定义与结构

对于一个 $m\times n$ 矩阵 $A$ ，设 $k=\operatorname{nnz}(A)$ 表示其在数学意义上的非零元素个数。其密度为 $k/(mn)$ ；若以零元素所占比例表示，则其稀疏度为 $1-k/(mn)$ 。稀疏矩阵与稠密矩阵之间不存在通用的密度分界值：实际如何区分，取决于存储开销、矩阵维度以及所执行的运算。稀疏表示不仅要存储数值，还要存储索引，因此并非所有含有零元素的矩阵都能通过这种方式节省存储空间。(mathworks.com)

稀疏模式是非零元素所在位置的集合。除了非零元素的数量，其排列方式也很重要：对角矩阵、带状矩阵、具有分块结构的矩阵和不规则矩阵，可能需要不同的存储策略。例如，一个 $n\times n$ 的单位矩阵只有 $n$ 个非零元素，密度为 $1/n$ 。这说明，一类矩阵可以随着维度的增大而变得越来越稀疏。(netlib.org)

有时需要区分数学意义上的非零元素与实际存储的条目。软件可能保留显式存储的零值或重复坐标，因此存储条目的数量不一定等于数学意义上的非零元素个数。在图相关应用中，显式存储的零值可以用来区分权重为零的连接与不存在的连接。(docs.scipy.org)

存储格式

稀疏数据结构需要在存储的紧凑性与构建、修改和访问的便利性之间作出权衡。以下几种格式应用广泛：

**坐标格式（COO）**存储行索引、列索引及对应的数值，便于将各个单独的贡献项组装成矩阵。重复坐标可以暂时保留，随后再合并。
压缩稀疏行（CSR），也称压缩行存储（CRS），按行组织条目。它使用一个数值数组、一个列索引数组，以及一个标记各行边界的行指针数组。
**压缩稀疏列（CSC）**采用类似的方式按列组织条目，使用行索引和列指针。
块稀疏格式记录小型稠密块，而不是单个标量元素。对角格式则存储选定的对角线及其偏移量。这些格式利用了矩阵中的规则结构，而通用坐标格式或压缩格式并不会显式编码这些结构。(docs.scipy.org)

以索引从零开始的 CSR 编码为例，

A=\begin{pmatrix} 4&0&7\\ 0&0&0\\ 2&5&0 \end{pmatrix}

可以表示为 values = [4,7,2,5]、column_indices = [0,2,0,1] 和 row_pointers = [0,2,2,4]。重复的指针值表明第二行为空。若有 $k$ 个存储条目，CSR 需要存储 $k$ 个数值、 $k$ 个列索引和 $m+1$ 个行指针：采用大O记号表示，其空间复杂度为 $O(k+m)$ ，而稠密存储为 $O(mn)$ 。(netlib.org)

算术运算与计算特性

一项基本运算是稀疏矩阵与向量的乘法。对于稠密向量 $x$ ，有

y_i=\sum_{j:A_{ij}\ne0}A_{ij}x_j.

按行组织的实现会遍历已存储的条目，而不是矩阵中的每一个位置。计入输出的初始化操作后，其时间复杂度通常为 $O(k+m)$ 。这项运算是迭代式线性方程组求解器的基本组成部分。(netlib.org)

并非所有运算都能保持稀疏性。加法可能合并两个稀疏模式，乘法可能产生更多非零元素，而稀疏矩阵的逆矩阵可能是稠密的。因此，通常不能仅根据输入矩阵的非零元素个数来推断稀疏矩阵乘法或方程求解的成本；输出结构和中间结果同样重要。(mathworks.com)

索引查找、间接内存访问和不规则的工作负载都会引入额外开销。专用算法即使减少了算术运算次数，也未必能使运行时间按相同比例缩短。存储格式和硬件特性都会影响性能，在并行计算中尤其如此。(netlib.org)

稀疏线性方程组的求解

稀疏矩阵经常出现于线性方程组 $Ax=b$ 中。直接法采用矩阵分解，例如LU分解或Cholesky分解。在消元过程中，原本为零的位置可能在分解因子中变为非零。这种现象称为填充，可能大幅增加内存占用和计算量。重新排列行和列可以减少填充，不过分解过程也受到数值方面要求的约束。(mathworks.com)

迭代法则通过反复执行运算来改进近似解，其中矩阵与向量的乘法往往占据主要计算量。共轭梯度法适用于对称正定方程组，其他方法则适用于不同类型的矩阵。预条件处理通过调整问题或迭代过程来改善收敛性；不完全分解是在限制填充的同时构造预条件子的一种方法。迭代次数不仅取决于稀疏性，还取决于谱性质、预条件子的有效性等因素。(netlib.org)

应用

对偏微分方程进行离散化通常会产生稀疏矩阵，因为局部方程只耦合邻近的未知量。例如，有限差分法会在相邻网格点之间形成具有规则结构的相互作用。稀疏方程组也常见于结构分析、电路分析、流体动力学和大规模数学优化。(mathworks.com)

在机器学习和自然语言处理中，文档—词项矩阵通常含有大量零元素，因为每篇文档只包含词汇表中的一小部分词项。因此，词袋模型及相关的加权表示适合采用稀疏存储。文本处理工具可以直接构建这些矩阵，无须先分配一个以文档为行、词汇为列的稠密数组。(scikit-learn.org)