LU decomposition

LU decomposition factors a matrix into a lower-triangular matrix and an upper-triangular matrix. It reduces many linear-system and determinant calculations to triangular solves.

Gaussian elimination: An algorithm that solves linear systems by using row operations to reduce their coefficient matrix. Its elimination steps produce the entries of the lower-triangular factor.
Linear system: A collection of linear equations sharing the same unknown variables. LU decomposition turns a system with a fixed coefficient matrix into two triangular solves.
Triangular matrix: A square matrix whose entries are zero either above or below its main diagonal. LU decomposition is defined by the triangular structure of both factors.
QR decomposition: A matrix factorization into an orthogonal matrix and an upper-triangular matrix. QR often offers better numerical stability for least-squares problems than LU.
Partial pivoting: A strategy that swaps rows to place a large-magnitude pivot in the elimination position. Row swaps make factorization more stable and can be necessary when a pivot is zero.
Repeated solution of linear systems: Solving multiple systems that share a coefficient matrix but have different right-hand sides. The factors can be reused, avoiding repeated elimination for each new right-hand side.
Elementary matrix: A matrix representing a single elementary row operation when multiplied on the left. Elimination can be expressed as a product of elementary matrices, revealing the lower factor.
Cholesky decomposition: A factorization of a symmetric positive-definite matrix as LLᵀ. For its restricted matrix class, Cholesky uses one triangular factor and is usually cheaper.
Permutation matrix: A square matrix that rearranges coordinates when multiplied by a vector. Pivoting records row exchanges in a permutation matrix, giving PA = LU.
Matrix inverse: The matrix that multiplies a square matrix to produce the identity matrix. Factored solves can compute inverse columns without treating inversion as a separate operation.

Linked from 14 pages