第 17 章起 · 稀疏与按需专题

书末部分转向工程专题：稀疏直接法、大规模 SVD、随机化算法与并行计算。这一节给出检索地图与要点。

稀疏直接法：排序决定一切

稀疏 LU/Cholesky 的填充（fill-in）由消元顺序决定，因此： 1. 排序（AMD、嵌套剖分）最小化填充； 2. 符号分解：预先算出非零结构； 3. 数值分解：按既定结构算数——排序只在符号阶段做一次。 对称正定稀疏 Cholesky + 好排序，在 $n\sim10^6$ 的网格问题上仍可用；三维问题的填充增长让纯直接法吃紧，这正是迭代法（CG+多重网格）的领地。

大规模 SVD 的三条路

• 小矩阵投影后 Golub-Kahan（Lanczos 双对角化 + 迭代）。
• 随机化 SVD：$\Omega$ 随机矩阵、$Y=A\Omega$、对 $Y$ 做 QR 后小规模 SVD——"随机投影抓列空间"，复杂度 $O(nnz(A)\cdot k)$，是今天大规模数据分解的主力（加幂迭代 $q\approx2$ 提升精度）。
• 增量/流式：数据太大不能落地时逐块更新分解。

并行矩阵计算的账

分布式内存下三本账：通信量、同步次数、负载均衡。三角求解难并行（依赖链长）是 LU 比矩阵乘慢的根源；分块与管道化（panel-broadcast）是 LAPACK/ScaLAPACK 的通用解法。

老师的提醒

• 稀疏求解器选型：对称正定 → CHOLMOD 类；一般 → MUMPS/SuperLU；迭代配合 → 先试多重网格预条件 CG。
• 大规模低秩问题（推荐系统、PCA）先想随机化 SVD，再想确定性算法——多数场景精度足够、速度快一个量级。

自检

• 稀疏直接法为什么把"排序"单独成阶段？
• 随机化 SVD 用几步矩阵-向量乘抓住列空间？
• 评判并行算法的三本账是什么？

更深一层：稀疏直接法的"图论本质"

稀疏 Cholesky 的填充问题本质是图论问题：矩阵的非零模式 = 无向图（行列 = 节点、非零元 = 边），Cholesky 消元 = 逐个删除节点并把其邻居两两连边（fill 边）。填充量由删除顺序决定——嵌套剖分（把图递归"分-治-缝"）与最小度（每次删当前度数最小者）是两大排序学派：前者对规则网格近乎最优（分治契合网格结构），后者对不规则结构灵活高效。理解了这层图论本质，三段式流水线（排序-符号-数值）就不再是流程规定而是必然：排序是图问题、只能做一次；数值是算术问题、可以反复做。

三维问题的坏消息也来自图论：三维网格的剖分树宽度大（$\sim n^{2/3}$），填充不可避免地 $\sim n^2$、内存 $\sim n^{4/3}$——$n = 10^7$ 时内存数百 TB。三维大规模问题最终都会走到迭代法门口，这不是算法偏好而是复杂度定理。

推导细读：随机化 SVD 为什么"一行随机性顶十年优化"

随机化 SVD 的误差保证（Eckart-Young 意义下接近最优）来自一个概率事实：随机向量以压倒性概率（$1 - c^{-k}$，$c$ 为过采样参数）与任何固定低秩子空间有足够大的投影分量。三个要点：过采样（取 $k + p$、$p \approx 10$ 列冗余，失败概率指数衰减）；幂迭代（$Y = (AA^T)^qA\Omega$，$q = 1\sim3$ 步把谱衰减快的方向进一步压掉——对奇异值衰减慢的矩阵必要）；正交化防塌缩。整套流程只有矩阵-向量乘与小型 QR——成本正比于"你想要的秩"，而非矩阵尺寸。这使它在大数据 PCA（$10^9\times10^4$ 矩阵）、天气降阶、分子动力学的协同振动分析里成为默认答案。

在真实世界里：并行矩阵计算的通信账本

并行数值线性代数的性能不由 flop 决定，由通信量、同步次数、负载均衡三本账决定。矩阵乘（通信/计算比好）几乎线性扩展；三角求解（依赖链长）是天然的并行噩梦——LU 比矩阵乘慢的核心原因在此。ScaLAPACK 的分块循环布局、通信避免算法（Communication-Avoiding QR 的 TS 矩阵重排）、任务数据流运行时（DAGuE）是三代的架构演进。给并行计算新人的三句话：先算通信再算 flop；让最强的机器做 Level-3；同步是全局税。

专题深入：稀疏直接法的"图论本质"展开

稀疏 Cholesky 的填充问题本质是图论：矩阵的非零模式 = 无向图，Cholesky 消元 = 逐个删除节点并把其邻居两两连边（fill 边）。填充量由删除顺序决定——嵌套剖分（把图递归"分-治-缝"）与最小度（每次删当前度数最小者）是两大排序学派：前者对规则网格近乎最优、后者对不规则结构灵活高效。三段式流水线（排序-符号-数值）的必然性：排序是图问题只能做一次、数值是算术问题可反复做——同一个矩阵多次分解时一二段成本全摊销。

三维问题的坏消息：三维网格的剖分树宽度大（$\sim n^{2/3}$），填充不可避免地 $\sim n^2$、内存 $\sim n^{4/3}$——$n = 10^7$ 时内存数百 TB。三维大规模问题最终都会走到迭代法门口，这不是算法偏好而是复杂度定理。

数学细节展开：随机化 SVD 的"一行随机性顶十年优化"

随机化 SVD 的完整流程值得作为"现代算法的范本"读：随机矩阵 $\Omega$ 投影 $Y = A\Omega$、对 $Y$ 正交化、在低维空间里精确分解——$O(nnz(A)\cdot k)$ 拿到 top-$k$ 奇异对。误差分析（Eckart-Young 意义下接近最优）来自"随机向量以压倒性概率与任何固定低秩子空间有足够大的投影分量"。幂迭代（$Y = (AA^T)^qA\Omega$）对奇异值衰减慢的矩阵必要。这套流程的全部成本只有矩阵-向量乘与小型 QR——这是它在大数据时代胜出的原因。

工程案例细节：并行矩阵计算的"三本账"

并行数值线性代数的性能三本账：通信量（数据移动的字节数——比 flop 更贵）、同步次数（全局同步是全局税）、负载均衡（最慢节点定总时间）。矩阵乘（通信/计算比好）几乎线性扩展；三角求解（依赖链长）是天然的并行噩梦——LU 比矩阵乘慢的并行根源在此。ScaLAPACK 的分块循环布局、通信避免算法（CAQR）、任务数据流运行时（DAGuE）是三代的架构演进。先算通信再算 flop；让最强的机器做 Level-3；同步是全局税——并行计算的三条军规。