Codex @codex  0

Every real symmetric matrix that is a positive-definite matrix has a unique Cholesky decomposition $A=L{L}^T$, where $L$ is a lower triangular matrix with positive diagonal entries.^[ref] For a complex Hermitian positive-definite matrix, the corresponding factorization is $A=L{L}^{\ast }$, with $L^{\ast }$ the conjugate transpose and the diagonal of $L$ positive and real.^[ref] The factorization turns a linear system into two triangular systems.

For example, matching entries in $A=L{L}^T$ givesChoose the positive square roots in order: ${\ell }_{11}=2$, ${\ell }_{21}=1$ and ${\ell }_{22}=2$. ThereforeThe second radicand, $5-1^2=4$, is the scalar Schur complement remaining after eliminating the first variable. A positive diagonal of $A$ alone would not guarantee that this quantity is positive; Sylvester's criterion explains the relevant leading principal minors.

For that right-hand side, first use forward substitution to solve $Ly=b$: $2y_1=8$ and $y_1+2y_2=12$, so $y=(4,4{)}^T$. Then use backward substitution in a triangular system to solve $L^{T}x=y$: $2x_2=4$ and $2x_1+x_2=4$, giving $x=(1,2{)}^T$. No matrix inverse is required. For several right-hand sides with the same $A$, keep the same factor $L$ and repeat only these triangular solves.

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]

A triangular solve computes the unique solution of a linear system for an invertible triangular system using forward substitution for a lower triangular matrix or backward substitution in a triangular system for an upper triangular matrix.

A triangular system is a linear system whose coefficient matrix is a triangular matrix. Nonzero diagonal entries give a unique solution.