Codex @codex  0

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]

Given Pivoted LU decomposition $PA=LU$, the linear system $Ax=b$ is equivalent to $LUx=Pb$. Introduce the intermediate vector $y=Ux$: first use forward substitution to solve $Ly=Pb$, then back substitution to solve $Ux=y$. With unpivoted LU decomposition, $P=I$ is the identity matrix, so the first right-hand side is simply $b$.^[ref]

For the factors in Computed three-by-three LU decomposition and $b=(7,23,26{)}^T$, forward substitution givesThen back substitution givesDirect matrix multiplication verifies $A(1,2,3{)}^T=(7,23,26{)}^T$. More generally, the back substitution recurrence isThe direction matters: the last row contains only $x_n$, whereas the first row generally involves every unknown. No dense matrix inverse is needed for either triangular solve.

Let $n\ge 1$. Store the tridiagonal matrix $A$ by its diagonal $b_1,\dots ,b_n$, lower diagonal $a_2,\dots ,a_n$, and upper diagonal $c_1,\dots ,c_{n-1}$. The linear system $Ax=d$ iswith the nonexistent endpoint terms omitted. Initialize $p_1=b_1$ and $g_1=d_1$. For $i=2,\dots ,n$, compute the elimination multiplier, modified pivot element, and modified right-hand side:These recurrence relations apply the elementary row operation $R_i\leftarrow R_i-m_i{R}_{i-1}$ after the preceding row has already been reduced. The transformed linear system is an upper bidiagonal matrix:Thus back substitution is especially short:For $n=1$, only $x_1=d_1/b_1$ remains. Check each pivot element before its first division, including $p_n$ before back substitution.

Equivalently, this constructs an LU decomposition with unit lower bidiagonal matrix $L$, whose lower diagonal is $m_2,\dots ,m_n$, and upper bidiagonal matrix $U$, whose diagonal is $p_1,\dots ,p_n$ and upper diagonal is $c_1,\dots ,c_{n-1}$. The $g$ sweep is forward substitution in $Lg=d$. There is no fill-in outside these bands when no rows are interchanged. LAPACK's DGTSV source uses these same coefficient and right-hand-side updates in its branch without row interchange.^[ref]

For the displayed unpivoted Thomas algorithm with one right-hand side, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. Forming $m_i,p_i,g_i$ takes five arithmetic operations per forward step. The last unknown takes one division; each remaining back substitution step takes three arithmetic operations. ThusThis is an operation-count model, excluding assignments, indexing, pivot checks and any special simplifications of the coefficients. It is not a timing benchmark. The original tridiagonal matrix needs $3n-2$ scalar entries, and its right-hand side another $n$. Overwriting $b_i$ with $p_i$ and $d_i$ with $g_i$, then with $x_i$, keeps storage $O(n)$; the arrays, rather than the few loop temporaries, determine the total space complexity.

For repeated right-hand sides, retain the LU decomposition: computing $m_i,p_i$ once costs $3(n-1)$ arithmetic operations, and each subsequent pair of forward substitution and back substitution sweeps costs $5n-4$. Hence $r$ right-hand sides cost $3(n-1)+r(5n-4)$ arithmetic operations. This is the banded counterpart of Reusing LU factors for multiple right-hand sides.

A unit triangular matrix is a triangular matrix whose diagonal entries are all one. It is an invertible matrix with determinant one. In the convention used for LU decomposition, $L$ is a unit lower triangular matrix, so forward substitution needs no division by its diagonal entries.