Scalar multifrontal elimination is equivalent to sparse Cholesky with column-count costs

For each vertex $v_r$, let $T_r$ be its subtree in the elimination forest and let $X_r=F_r\setminus \{v_r\}$. Define the local matrix for $T_r$ on $T_r\cup X_r$ to contain exactly the original entries assigned to fronts in $T_r$; its $X_r\times X_r$ block is zero, since entries wholly within $X_r$ are assigned to later fronts. If $u\in T_r$ and $w\mathrm{\notin }{T}_r\cup X_r$ had an original edge, then either $w$ is earlier than $u$, making $u$ a later filled neighbor and ancestor of $w$, which would put $w$ in $T_r$, or $w$ is later than $u$, making $w$ a later filled neighbor and ancestor of $u$. In the latter case, repeated application of the child-column containment in [F2] from $u$ up to $v_r$ puts $w$ in $F_r$; since $w\mathrm{\ne }{v}_r$ and $w\mathrm{\notin }{T}_r$, it belongs to $X_r$. Both cases contradict the choice of $w$ by [F2,F3]. The induction invariant is that the returned array is the Schur contribution on $X_r$ after eliminating $T_r$ from this local matrix. If $v_r$ is a leaf, every entry assigned to its front has at least one endpoint $v_r$, so its initialized front is exactly this local matrix, with zero external-external block. The scalar update $C-b{b}^{\ast }\mathrm{/}d$ therefore returns its Schur contribution.

Let $v_r$ have children $v_{s_1},\dots ,v_{s_q}$. By [F2], each child interface $X_{s_h}$ lies in $F_r$, so every extend-add is defined. By [F3], there is no original matrix coupling between interiors of distinct child subtrees: such an edge would make its later endpoint a filled neighbor outside the earlier endpoint's parent path. Form the local matrix on the union of those child interiors and $F_r$, using only original entries assigned to these child subtrees or to $v_r$ and leaving entries wholly in $X_r$ zero. Its child-interior block is $D=\mathrm{diag}(D_1,\dots ,D_q)$, and its coupling to the current front is $B=[B_1\cdots B_q]$ partitioned by child subtree. Each $D_h=A[T_{s_h},T_{s_h}]$ is a principal submatrix of the positive-definite $A$, so it is positive definite; [F5] gives a Cholesky factor with positive diagonal and therefore shows $D_h$ is nonsingular. Its Schur complement on the current front is $C-B{D}^{-1}{B}^{\ast }=C-{\sum }_h{B}_h{D}_h^{-1}{B}_h^{\ast }$. The correction $-B{D}^{-1}{B}^{\ast }=-{\sum }_h{B}_h{D}_h^{-1}{B}_h^{\ast }$ is exactly the sum of child contributions by the induction invariant; adding them to the entries assigned to $v_r$ assembles this same local Schur complement. The pivot update $C-b{b}^{\ast }\mathrm{/}d$ then eliminates $v_r$ and proves the invariant for $T_r$.

The invariant at each root eliminates all vertices. Each pivot column is therefore computed from the same exact Schur complement as scalar elimination in $\pi$, so the multifrontal factors equal the scalar Cholesky factors.

Front $r$ has $d_r={\mathrm{\ell }}_r+1$ indices. Its dense scalar pivot update and initialization from assigned entries use at most a constant multiple of $d_r^2$ arithmetic operations. Embedding and adding a child contribution touches at most that child's dense trailing block, whose entries are already counted by the child's $d_s^2$ bound. Summing over fronts gives $O({\sum }_r{d}_r^2)$ arithmetic work. By [F1], each factor column retains one diagonal slot and all ${\mathrm{\ell }}_r$ later-neighbor slots, including structural zeros, so symbolic factor storage is exactly ${\sum }_r{d}_r$.

The forward column updates in [F1] solve $Lx=Pb$: after column $j$ is processed, row $j$ satisfies its equation, and the pivot contribution has been subtracted from each later row. This is the unique solution in [F4]. The descending conjugate updates solve $L^{\ast }y=x$ by the backward recurrence in [F4]. Since $PA{P}^{\ast }=L{L}^{\ast }$, these equations imply $PA{P}^{\ast }y=Pb$; multiplying by $P^{\ast }$ gives $A(P^{\ast }y)=b$. Thus $P^{\ast }y$ is the unique solution of $Az=b$.

Each stored off-diagonal factor entry is visited once in each triangular solve, with one multiply and one subtraction; each diagonal contributes one division. Hence the two solves use $O(n+{\sum }_r{\mathrm{\ell }}_r)=O({\sum }_r{d}_r)$ operations, separate from the factorization work in step 3.2.

Step 3.1 gives scalar equivalence, step 3.2 gives factorization work and factor storage, and steps 4.1–5.1 give solve correctness and work.