嵌套剖分消元顺序

分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。中的“分别解决”在这里有严格的图依据。内部点被消去时，新增边只能连接其当前邻居。不同子域之间没有原边，而分隔器还没有被消去，因此不存在经过已消去节点、跨越两个子域的路径。填充可以到达界面，却不能穿过尚未消去的界面继续把其他子域搅在一起。

若反过来先消去整个十字分隔器，它的邻居会被补成团，原本独立的四个角区就提前连通。几何上看似“先把中间清空”，在线性代数上却可能制造更多耦合。

为什么二维存储与算术有不同阶数 ​

深度 $\ell$ 约有 $4^{\ell }$ 个子域，每个边长约 $q/2^{\ell }$。它的本层分隔器，以及与祖先分隔器相接的边界，总规模均为 $O(q/2^{\ell })$。这里利用规则局部网格：一个小方块接触外界的点沿其边界分布，不会与整条远处祖先分隔器全部直接相接。

把这一界面前沿按稠密块上界估计，存储是边长平方，算术是边长立方。因此第 $\ell$ 层分别贡献

共有 $O(\log q)$ 层，所以因子结构存储为 $O(N\log N)$；算术量按几何级数求和，为 $O(q^3)=O(N^{3/2})$。叶子工作也被这些界包含。这不是把每层都当成一个 $N$ 阶稠密问题，而是在数一批逐渐缩小的界面块。

一份可复现的七乘七次序 ​

用 $(r,c)$ 表示网格位置，$0\le r,c<7$，自然编号为 $7r+c$。最外层分隔器是 $r=3$ 或 $c=3$ 的十三个点。四个角区各是 $3\times 3$，再各取一条五点十字，最后剩下单点叶子。

固定子域遍历为左上、右上、左下、右下；同层分隔器按自然编号追加。于是先输出左上 $3\times 3$ 的四个角 $(0,0),(0,2),(2,0),(2,2)$，再输出其五点十字；然后依次处理另外三个角区，最后才输出全局十三点十字。这明确了全部 $49$ 个节点的次序，脚本另外保存完整编号列表。

逐轮运行邻居补团算法，得到以下结构计数。平方和 $W=\sum _j(d_j+1{)}^2$ 是比较消元算术量的统一指标，不把它误称为某个机器实现的精确 FLOP 数。

例如七乘七原图有 $2q(q-1)=84$ 条边，原下三角含对角为 $49+84=133$ 项。自然序增加 $216$ 条边成为 $349$ 项；嵌套剖分增加 $155$ 条边成为 $288$ 项。两种统计使用同一结构定义，没有借助数值相消减少其中一方。

自然行序在规则网格上形成约 $q$ 宽的长消元前沿，大量列都有 $\mathrm{\Theta }(q)$ 个后继，因而存储为 $\mathrm{\Theta }(Nq)=\mathrm{\Theta }(N^{3/2})$、算术为 $\mathrm{\Theta }(N{q}^2)=\mathrm{\Theta }(N^2)$。嵌套剖分的收益来自大前沿只出现在少数高层，而不是所有列都大。

维数与几何条件不能省略 ​

三维 $q^3$ 网格的分隔器是面积规模 $O(q^2)$，同样的逐层计数给出 $O(N^{4/3})$ 存储与 $O(N^2)$ 算术。二维的近线性存储结论不能直接搬到三维。

一般图也可能使用分隔器算法，但“找到一个小分隔器”并不足以自动得到本页递推。需要递归子图都保持合适的平衡分隔性质，并控制已有界面的传播。十字切法只适用于有相应规则几何的图；它不是任意稀疏矩阵的通用最优排列。

排序阶段可以直接从规则网格索引生成本例列表，递归扫描的朴素实现需 $O(N\log N)$ 时间；利用坐标范围与直接输出可进一步减少扫描。一般图寻找分隔器的成本必须单列，不能并入“每层免费划分”的假设。

子域优先的次序也影响消元树公理库消元树与稀疏列依赖Elimination tree · Cholesky elimination tree从因子每列首个下方结构位置构造父指针，证明非零必指向祖先，并用两条独立子链解释依赖、并行与祖先判据的单向性。：不同子域的列可并行处理，较晚的分隔器接收它们的更新。实际直接求解器常把多列合成前沿或超节点，以稠密块操作提高效率；数学填充界没有包括通信、同步与缓存等常数成本。

选择排列时，应同时记录设置开销、结构位置数、列大小分布和数值分解时间。嵌套剖分保证的是适当模型下的好界，不承诺每个小实例都比所有局部启发式更省。