稀疏 Cholesky 的消元图与符号分解

Schur 补公理库Schur 补与静态凝聚Schur complement · Static condensation把内部变量的精确响应折入界面矩阵与右端，推导 Schur 补、恢复公式及最小能量性质，并逐项凝聚五节点链。说明，消去 $j$ 会对剩余系数执行

只要 $u,v$ 都与 $j$ 耦合，乘积就有可能非零。图算法把“有可能”记成一条边，不提前猜测它是否会与原项抵消。这使同一模式的多次数值分解能够共享一次符号分析。

一条跨越多步的路径判据 ​

对 $i>j$，位置 $L_{ij}$ 是结构非零，当且仅当原图中存在从 $j$ 到 $i$ 的路径，其所有内部顶点编号都小于 $j$。直接原边对应没有内部顶点的路径。

证明可随消元归纳。消去 $k$ 时，新增边 $uv$ 来自 $u-k-v$；若两条已有边已经分别代表经过更小编号点的路径，把它们接起来就得到内部点不超过 $k$ 的通路，再去掉重复顶点即可。反方向，给定一条内部点都将先被消去的路径，逐个消去这些内部点会把路径缩短，最终留下端点边。

这个判据解释了为何填充不只是“原矩阵两步路径”的一次统计。早先产生的边还会参与以后消元，把长路径的作用继续传递。

同一六节点图，两份完整账本 ​

原边为六环 $01,12,23,34,45,50$ 加弦 $14$，共七条边。自然顺序 $0,1,2,3,4,5$ 给出：

所以逐列行号是

按列接起来有 $17$ 项；从零开始的 CSC 列指针为 $(0,3,7,11,14,16,17)$。原矩阵下三角含对角有 $6+7=13$ 项，四条填充恰好使它增加到 $17$。

改用原顶点顺序 $\pi =(0,2,5,3,1,4)$。先消去 $0$ 添边 $15$，再消去 $2$ 添边 $13$；随后 $5$ 的剩余邻居是 $1,4$，二者原本已经相连，$3$ 的剩余邻居也相同，均无新增边。最后消去 $1,4$。这次只有两条填充，共 $15$ 个因子位置。

注意排列后列号已经改变。按新位置记录的列集合是

第一列中的行 $2,4$ 分别对应原顶点 $5,1$。如果一边用原顶点号画图，一边把它直接当 CSC 行号，就会把正确的消元过程存成错误矩阵。

结构存在，数值也可以恰为零 ​

取正定矩阵

原图是三角形，所以符号预测包含 $L_{21}$。但消去第零列后，剩余非对角项为 $1-1\cdot 1=0$，实际因子为

符号位置 $L_{21}$ 可以存一个数值零。这是安全的结构上界，并不构成预测失败。反过来，不能因为这一次相消，就在后续系数变化时继续省略该槽位。

记 $d_j=|N_j|$。因子的结构存储恰为

一次稀疏右看式数值消元要更新 $d_j\times d_j$ 的对称子块，因此工作尺度为 $\mathrm{\Theta }(\sum _j(d_j+1{)}^2)$；若只数下三角乘减更新，次数是 $\sum _j{d}_j(d_j+1)/2$，另有对角处理和缩放。上例两种顺序的平方和分别为 $55$ 与 $41$，对称更新次数为 $19$ 与 $13$。非零数相近的两个因子，也可能因大列分布不同而有不同算术量。

朴素补团实现枚举这些邻居对。在哈希邻接集合的平均常数操作假设下，时间为 $O(n+m+\sum _j{d}_j^2)$，保存图和列模式需要 $O(n+m+\text{fill})$ 空间；使用平衡集合则还需计入查找插入的对数因子。更好的符号算法利用消元树公理库消元树与稀疏列依赖Elimination tree · Cholesky elimination tree从因子每列首个下方结构位置构造父指针，证明非零必指向祖先，并用两条独立子链解释依赖、并行与祖先判据的单向性。压缩依赖，不能把它们的复杂度直接赋给这份朴素实现。

排列的价值是改变未来邻居集，而不只是让图看起来整齐。嵌套剖分公理库嵌套剖分消元顺序Nested dissection ordering递归把二维网格分隔器排在子域之后，用完整填充账本与逐层前沿计数推导存储和算术界，并说明三维为何更昂贵。把分隔器排到最后；不完全分解则主动拒绝保存某些填充，二者分别改变精确消元的次序与数值近似的规则。

本页依赖正定问题不需数值选主元。若一般 LU 为稳定性临时交换行列，实际消元顺序可能偏离预先计划，不能照搬固定排列下的精确模式结论。