消元树与稀疏列依赖

一列消完后，它的剩余邻居已被补成团。其中编号最小的邻居先被处理，可以接收这一列的贡献，再把需要继续传递的信息送向更晚的邻居。父边正是这个最早接收者。

为什么每个因子非零都通向祖先 ​

设 $L_{ij}$ 为结构非零，令 $p=\mathrm{parent}(j)$。若 $p=i$，结论成立；否则 $j<p<i$。消去 $j$ 时，$p$ 与 $i$ 同为剩余邻居，所以二者被连接。到消去 $p$ 时，位置 $L_{ip}$ 仍在结构模式内。

于是问题从 $(j,i)$ 转成 $(p,i)$。继续取父节点，编号严格增加且不超过 $i$，有限步后必到 $i$。这也说明完整更新依赖 $j\to i$ 可以沿父路径传递，父数组没有漏掉必要的先后约束。

证明使用结构边，不依赖某次计算中的系数恰好非零。若数值相消使一条实际更新为零，预先保留的树仍是安全的调度依据。

取七个顶点，原边为

即两条链 $0-1-2-6$ 与 $3-4-5-6$ 在顶点 $6$ 汇合。可以用 $A=I+L_G$ 实现一个具有此图的正定矩阵，其中 $L_G$ 是图 Laplacian；单位阵使常量方向也有正能量。

按 $0,1,2,3,4,5,6$ 消元，每次当前节点只有一个尚存邻居，所以没有填充。模式与父指针如下：

第 $0$ 列必须先于第 $1$ 列，第 $1$ 列先于第 $2$ 列；另一侧相应是 $3\to 4\to 5$。两侧可以同时推进，根 $6$ 等待两条子链的贡献都到达。

但 $2$ 是 $0$ 的祖先，$L_{20}$ 却不在模式中；$6$ 也是 $0$ 的祖先，$L_{60}$ 同样不在模式中。父路径记录间接依赖，不会自动把所有祖先变成直接因子位置。

树高、列大小与并行成本 ​

本例的两个子树没有相互依赖，可独立计算局部更新。不过它们都向根贡献数值，汇合时仍需归约或同步。“子树独立”不表示多个线程可以不加控制地同时写同一块数组。

若把同一无分支链按自然次序消元，消元树也会是一条长链，串行依赖深。重排序可能让树更平衡，但树高不是唯一指标：一个很宽的树若在根部汇集极大稠密前沿，最终的算术量和内存仍可能主导时间。要同时看每个节点对应的列大小、工作权重和可用并行度。

如果图不连通，各连通分量独立产生一棵树。人为添加一个没有数值自由度的超级根可以方便遍历，但不应把它当成额外矩阵列或给它增加因子非零。

先由父指针建立每个节点的孩子列表，再从各根沿孩子方向做深度优先遍历公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。，按退出顺序获得后序：孩子先于父亲，所有依赖方向都一致。后序可帮助安排工作与聚集子树数据；它本身不重新求最小填充排列，也不把任何正序编号都变成相同的数值算法。

树还可以配合原矩阵模式做结构可达性查询，避免显式遍历所有已填充图边。此时必须保留原边信息：仅凭“祖先”判据无法恢复因子模式，正如上例所示。

嵌套剖分公理库嵌套剖分消元顺序Nested dissection ordering递归把二维网格分隔器排在子域之后，用完整填充账本与逐层前沿计数推导存储和算术界，并说明三维为何更昂贵。先消去分离子域、最后处理分隔器，往往产生适于子树并行的依赖结构。它的分隔器树以一整组顶点为节点，消元树则以单列为节点；两者可以相互解释，但不是同一个数据对象。