稀疏矩阵方法

当一个矩阵绝大多数元素为零时，它就是稀疏的——想象一个百万乘百万的矩阵，每行只有寥寥几个非零元，正是离散化偏微分方程、网络和图所产生的那一类。存储所有那些零、或用它们做算术，都荒谬至极。稀疏矩阵方法就是只触及非零元的存储格式与算法，把一个不可能的问题变成寻常之事。

第一个思想是表示。不存满的 n 乘 n 数组，而只存非零值及其位置。常见格式包括坐标表（COO：行、列、值的三元组）、压缩稀疏行（CSR：值加列索引加行指针）和压缩稀疏列（CSC）。于是矩阵-向量乘积只需 O(nnz)，正比于非零元个数而非 n^2——往往是巨大的节省。

第二个思想是在计算过程中保持稀疏性。这里直接法碰壁了：分解一个稀疏矩阵会制造填入，即在 L 和 U 因子中由零变为非零的元素，有时是灾难性的。稀疏直接求解器通过在分解前重排行列（最小度、嵌套剖分排序）来对抗它，以最小化填入。即便如此，填入仍可能在最大的问题上耗尽内存。

这正是迭代 Krylov 方法在大规模上占主导的原因。共轭梯度和 GMRES 只需矩阵-向量乘积，它们完美尊重稀疏性且从不制造填入，故其内存自始至终保持在 O(nnz)。配上稀疏预处理子，它们能解出有数百万乃至数十亿未知数的系统，那是任何直接法都无法分解的。稀疏性正是迭代哲学在大规模科学计算中取胜的结构性原因。