稀疏矩阵

稀疏矩阵是指矩阵中绝大多数元素为零的矩阵。与稠密矩阵（大多数元素非零）相比，稀疏矩阵通过仅存储非零元素及其位置，可大幅节省内存并提高计算效率。这一概念在计算数学中尤为重要，因为许多科学计算问题（如偏微分方程离散化、网络分析、机器学习等）天然具有稀疏性。

1. 稀疏性的定义与意义

• 定义：若矩阵中非零元素的数量远小于零元素的数量（通常非零元素占比低于5%），则称其为稀疏矩阵。
• 意义：
  • 存储优化：稠密矩阵存储需占用 \(O(n^2)\) 空间，而稀疏矩阵仅存储非零元素（如坐标列表格式需 \(O(\text{nnz})\) 空间，其中 \(\text{nnz}\) 为非零元素个数）。
  • 计算加速：算法可跳过零元素操作，降低时间复杂度（如矩阵向量乘法从 \(O(n^2)\) 降至 \(O(\text{nnz})\)）。

2. 稀疏矩阵的存储格式

不同存储格式针对特定操作（如矩阵乘法、求解线性系统）优化：

• 坐标格式（COO）
  • 存储三个数组：行索引、列索引、非零值。
  • 优点：灵活易构建；缺点：不适合直接进行数值运算。
• 压缩行存储（CSR）
  • 存储三个数组：非零值、列索引、行指针（记录每行起始位置）。
  • 优点：高效支持矩阵向量乘法；缺点：插入新元素成本高。
• 压缩列存储（CSC）
  • 类似CSR，但按列压缩，适用于列操作。
• 对角线存储（DIA）
  • 适用于非零元素集中在对角线附近的矩阵（如有限差分矩阵）。

3. 稀疏矩阵的运算特性

• 矩阵向量乘法（SpMV）：
  • 关键操作，在迭代法（如共轭梯度法）中频繁使用。
  • CSR格式下，按行遍历非零元素，仅计算非零部分。
• 线性求解：
  • 直接法（如稀疏LU分解）可能引入填充元（fill-in），需重排序优化（如AMD算法）。
  • 迭代法（如Krylov子空间方法）依赖SpMV，适合大规模稀疏问题。

4. 稀疏性与算法设计

• 填充元控制：在稀疏LU或Cholesky分解中，通过行列重排序（如最小度算法、嵌套剖分）减少非零元增长。
• 预条件技术：
  • 构造稀疏近似逆（SPAI）或不完全分解（ILU）作为预条件子，加速迭代收敛。
• 并行计算：
  • 稀疏矩阵运算常需不规则内存访问，需结合负载平衡（如图划分）实现高效并行化。

5. 应用场景举例

• 偏微分方程数值解：有限差分/有限元离散化产生带状稀疏矩阵。
• 图论问题：邻接矩阵通常稀疏，如社交网络分析。
• 数据科学：特征矩阵中多数特征值为零（如文本TF-IDF矩阵）。

通过理解稀疏矩阵的存储与运算特性，可针对具体问题选择最优格式和算法，实现计算资源的高效利用。这一概念是连接理论模型与大规模数值计算的关键桥梁。