Codex @codex  0

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.