Codex @codex  0

Fill-in consists of new nonzero positions created by Gaussian elimination, absent from the original sparse matrix in the same ordering. For a Cholesky decomposition $PA{P}^T=C{C}^T$, compare $C$ with the lower triangle of $PA{P}^T$, not with the unpermuted input. Each new undirected edge of the elimination graph contributes one structural position in $C$. The sparse elimination of a four-leaf star gives six such positions when the center is eliminated first, and none when the leaves are eliminated first.

Symbolic factorization predicts possible nonzeros from the pattern alone. An initially zero $a_{ij}$ becomes nonzero in a single scalar step if both $a_{ik}$ and $a_{kj}$ are nonzero; however, at later steps several contributions can cancel. For an exact example, letEliminate indices $1,2$ in that order. The first Schur complement, in order $(2,3,4)$, isThe second pivot element updates the $(3,4)$ entry to $-1/3-(-1/2)(1)/(3/2)=0$. The remaining block is $\mathrm{diag}(7/3,7/3)$, so all four pivot elements are positive and $H$ is a symmetric positive-definite matrix. The elimination graph retains the structural edge $3-4$, but this exact choice of coefficients makes the numerical entry vanish. A small change to $H_{34}=H_{43}$ generally removes the cancellation.

Such an exact zero is different from discarding a small value computed with floating-point arithmetic. The symbolic factorization deliberately reserves space for possible entries without depending on special numerical identities. A perfect elimination ordering creates no structural fill-in at all; an ordering with cancellations need not have that property.

Associate an undirected graph with a symmetric matrix's off-diagonal nonzero pattern. Eliminating vertex $i$ updates the remaining matrix by $a_{jk}\mapsto a_{jk}-a_{ji}{a}_{ik}/a_{ii}$. Only pairs of neighbors of $i$ can acquire fill-in. If the graph is a tree, remove leaves successively: each eliminated vertex has at most one remaining neighbor, so only a diagonal entry can change. Every Schur complement of a positive-definite matrix is positive definite, so no zero pivot forces a different ordering. Leaf removal therefore constructs a perfect elimination ordering and a fill-free factorization.

Maximum cardinality search is a graph search in which an unselected vertex's score counts its already selected graph neighbours. Repeatedly select a vertex of maximum score, breaking ties arbitrarily, and update its unselected graph neighbours. On a chordal graph, the reverse selection order is a perfect elimination ordering. On $C_4$, selecting $(a,b,c,d)$ instead yields candidate deletion order $(d,c,b,a)$; $d$'s later graph neighbours $a,c$ are not adjacent, so the clique check fails.^[ref]

Use the undirected graph of the symmetric off-diagonal sparsity pattern. Reading the original matrix gives the edgesThis connected nine-vertex, eight-edge graph is a tree. A leaf-removal perfect elimination ordering isThe corresponding lists of remaining neighbors are, in order, $\{1\},\{8\},\{7\},\{7\},\{5\},\{4\},\{1\},\{1\},\varnothing$. Thus simultaneous row and column permutation to this ordering allows Gaussian elimination without fill-in.

Here are the precise facts that justify the procedure. First, eliminating index $i$ makes the remaining entriesOnly pairs of remaining neighbors of $i$ can acquire a new nonzero entry. Consequently a vertex whose remaining neighbors form a clique can be eliminated without structural fill. Such a vertex is simplicial. An ordering in which each successive vertex is simplicial is a perfect elimination ordering. The graph characterization says that a graph admits such an ordering if and only if it is a chordal graph, meaning every cycle of length at least four has a chord. A tree has no cycles; more concretely, every nontrivial finite tree has a leaf, and removing a leaf leaves a forest. These statements explain why successive leaf removal works here without having to find a general-purpose chordal ordering.

Second, for a symmetric positive-definite matrix, every diagonal pivot and every successive Schur complement is positive definite. For example, if the first pivot is $a_{ii}$ and its coupling column is $b$, then for any nonzero remaining vector $x$,Thus no zero pivot requires abandoning the proposed ordering. Since each eliminated vertex here has at most one remaining neighbor, its Schur update changes only a diagonal entry. This proves the claimed fill-free LDL decomposition or Cholesky decomposition for every positive-definite matrix with the given pattern, including cases with additional accidental zeros. It is leaf elimination of a tree-pattern positive-definite matrix.

Sparse Gaussian elimination seeks a direct solution while preserving the advantage of a small number of nonzeros. The main issue is that eliminating unknowns creates new interactions between the remaining unknowns. For a symmetric positive-definite system, simultaneous row and column permutation merely changes the elimination order, and Cholesky decomposition or LDL decomposition can proceed without pivoting. Partition one elimination step asThe remaining system has the Schur complement $C-b{b}^T/a$. It is positive-definite because, for any nonzero $z$, minimizing the positive quadratic form of $A$ over the first coordinate gives $z^T(C-b{b}^T/a)z>0$. This both justifies the next positive pivot and identifies exactly where fill can appear.

The matrix graph of a symmetric sparsity pattern has one vertex per unknown and an edge $i-j$ when $a_{ij}$ is structurally nonzero. At pivot $k$, the updatecan change an entry only when both $i$ and $j$ are current neighbors of $k$. Thus the elimination graph operation removes $k$ and makes its remaining neighbors a clique. Edges absent before this update are fill-in. The graph describes structural or generic nonzeros: special cancellations in the numerical values can reduce the actual fill, but cannot justify omitting possible entries in advance.

A useful global description is the fill-path criterion for symmetric elimination. After a set $E$ has been eliminated, remaining vertices $i,j$ are adjacent generically exactly when their original graph contains a path from $i$ to $j$ with all internal vertices in $E$. The assertion starts with the original edges when $E$ is empty. Eliminating the next vertex concatenates two earlier such paths through it; conversely, split any allowed path at the newly eliminated vertex to recover the two earlier connections. This induction explains why sparse long-range couplings may eventually become dense.

The order is decisive. For a star with four leaves, eliminating a leaf only changes the diagonal of its sole neighbor and creates no fill. Repeated leaf elimination preserves this property. Eliminating the central vertex first instead connects all four leaves, creating six edges and a dense four-variable trailing system. This occurs, for example, in a positive-definite star matrix with central diagonal $5$, leaf diagonals $2$ and edge entries $-1$; no cancellation removes the new leaf couplings.

For an arbitrary graph, an ordering creates no fill precisely when each pivot's later neighbors are already a clique, namely a perfect elimination ordering. Such an ordering exists exactly for a chordal graph. A chordless cycle of length at least four illustrates the obstruction: its first removed vertex connects its two previously nonadjacent neighbors. Eliminating in a chosen order adds chords until the completed graph is chordal. Thus sparsity of the original matrix alone does not guarantee sparse factors; the graph and its ordering matter together.

If pivot $j$ has $d_j$ later neighbors, its column contains $d_j+1$ factor entries and its symmetric outer-product update costs $O(d_j^2)$ arithmetic. The total storage is governed by ${\sum }_j(d_j+1)$ and the work by ${\sum }_j(d_j+1{)}^2$. A band ordering with matrix bandwidth $b$ gives the familiar $O(Nb)$ storage and $O(N{b}^2)$ work, but a narrow profile or graph separator can do better than a single global band. The minimum degree algorithm greedily chooses a current low-degree pivot; it often keeps immediate updates small, but it must account for previously created fill and need not minimize total fill.

Nested dissection instead finds a small vertex separator, recursively eliminates disconnected subdomains, and leaves separator variables until last. For a regular two-dimensional grid with $N$ unknowns, a separator has $O(\sqrt{N})$ vertices. Its dense final work is $O(N^{3/2})$, and recursive balanced separation givesAt each level the summed separator-square storage is $O(N)$, giving $O(N\log N)$ factor storage over the logarithmic number of levels. These estimates assume the usual geometric separator structure; they are not guarantees for every sparse graph. Independent subdomains also expose parallel work.

In a practical solver a symbolic factorization phase uses the pattern and ordering to allocate factor storage and schedule updates. For the lower-triangular factor, the elimination tree takes the parent of column $j$ to be its first later row index containing a structural nonzero. Descendant updates flow towards those later pivots, making the tree useful for dependency scheduling and the organization of the factorization. Compressed sparse storage records only entries and indices; the numerical phase then computes the values, followed by forward and backward substitution. The factors can be reused for many right-hand sides.

Finally, structural efficiency must be balanced with numerical stability. For a nonsymmetric system the pattern can be represented by a directed or bipartite graph, and elimination creates edges from incoming to outgoing neighbors. Separate row and column permutations are possible. A fill-reducing column ordering does not ensure a safe pivot: scaling and partial pivoting may be needed to prevent division by a tiny number and large growth. Such row interchanges can change the predicted fill. Positive-definite symmetric problems avoid this conflict; general sparse solvers must manage it explicitly. Graph-based ordering controls factor sparsity, while pivoting controls numerical safety; an effective sparse factorization needs both.

A valid triangulation of an undirected graph adds exactly the two fill edgesTo verify it, eliminate the vertices in the order $P,Q,R,S,X,Y,B,D,F,M,A,C,U,V$. The first eight eliminations have neighboring vertices already joined. When $F$ is eliminated, its remaining neighbors are $A,M$, so add $AM$. When $M$ is eliminated, its remaining neighbors are $A,C$, so add $AC$. The remaining $A,C,U,V$ form a clique.

Thus this order is a perfect elimination ordering of the completed graph, which is a chordal graph. The fill edges are computational devices for genotype elimination; they do not add parent-child relationships to the pedigree.

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]

Sparse Gaussian elimination solves a linear system by Gaussian elimination while exploiting its sparse matrix structure to avoid storing zeros and performing unnecessary arithmetic operations. The catch is that zeros in the input need not remain zero: eliminating a shared unknown can couple two equations that previously had no direct coupling. These new positions are fill-in, and their number can depend strongly on the order of elimination.

For a real symmetric positive-definite matrix, the usual direct method is a Cholesky decomposition. Choose an ordering, use symbolic factorization to allocate the predicted factor entries, compute their values, then solve two triangular systems. Compressed sparse storage makes the reduced storage useful. General LU decomposition may also need numerical partial pivoting, so an ordering chosen for sparsity can change during factorization.^[ref]

For a fixed ordering, let $P$ be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here $C$ is the lower triangular matrix in the Cholesky decomposition of $B$; $z=Px$. Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because $v^{T}Bv=(P^{T}v{)}^{T}A(P^{T}v)>0$ for every nonzero vector $v$. A row permutation alone generally loses the symmetric matrix structure.

The local mechanism is a Schur complement. If the active pivot element is $a_{kk}$, then for remaining indices $i,j$,Even when $a_{ij}=0$, two nonzero couplings through $k$ make the second term nonzero. Thus the elimination graph removes $k$ and joins its remaining neighbors into a clique. The fill-path criterion for symmetric elimination extends this local rule across several steps. The elimination tree organizes the resulting dependencies; the minimum degree algorithm and nested dissection choose orderings to control them.

This connection between graphs and linear systems was already explicit in Donald J. Rose, R. Endre Tarjan and George S. Lueker's 1976 study of fill-in and perfect elimination orderings.^[ref]

Triangulation adds fill edges to an undirected graph to make it a chordal graph. Given an elimination ordering, join all remaining neighbors of each removed vertex. The completed graph has that perfect elimination ordering. Fill edges can enlarge the cliques used for exact probabilistic graphical model inference, without changing the original probability factors; they do not assert new biological relationships.