Contents

Lu FactorizationEdit

LU factorization is a central tool in numerical linear algebra for decomposing a square matrix into a product of simpler, well-understood pieces. In its most common form, a matrix A is written as A = LU, where L is lower triangular and U is upper triangular. In many practical implementations, L is taken to be a unit lower triangular matrix (diagonal entries equal to 1) so that the decomposition is determined entirely by the off-diagonal structure of L and the diagonal of U. To handle a broad class of matrices and improve numerical stability, a permutation of rows is often incorporated, yielding PA = LU, where P is a permutation matrix. This combination is the workhorse behind direct methods for solving systems of linear equations and for performing matrix-inverse and determinant calculations. See Gaussian elimination for related procedures and permutation matrix for row-swapping operations.

In solving a linear system Ax = b, the LU decomposition enables a two-step process: first solve Ly = Pb by forward substitution, then solve Ux = y by backward substitution. This approach is especially advantageous when multiple right-hand sides are involved, because the factorization P, L, and U can be computed once and reused. See forward substitution and backward substitution for the core techniques, and linear system for the broader problem setting.

LU factorization sits within the broader scope of direct methods for linear systems and is closely related to other matrix factorizations and numerical methods. It is especially important in contexts where the matrix has to be reused to solve multiple systems, or when one needs to compute the determinant or the inverse efficiently from the same factorization. See determinant and inverse of a matrix for related topics, and dense matrix or sparse matrix depending on the storage pattern of A.

Existence and forms

Basic idea

The goal is to express A as a product of a lower-triangular matrix L and an upper-triangular matrix U. In the Doolittle form, L is unit lower triangular and U is upper triangular; in the Crout form, U is unit upper triangular while L carries the diagonal. The choice of form affects convention and implementation but not the fundamental idea of a triangular factorization. See Doolittle method and Crout method for concrete procedures and historical background.

Conditions for existence

Without row permutations, an LU decomposition A = LU exists if all leading principal minors of A are nonzero. In practice, many matrices encountered in applications do not satisfy this property, but a row-permuted version PA = LU exists for a wide class of matrices, with P chosen to avoid zero pivots during elimination. See pivoting and Gaussian elimination for the mechanics behind these conditions.

Pivoting and LU with permutations

Row pivoting (partial pivoting) selects the largest available pivot in a column to maintain numerical stability and to avoid division by very small numbers. More aggressive strategies (complete pivoting) consider all remaining submatrix elements to maximize numerical robustness, at the expense of additional bookkeeping and data movement. The use of a permutation matrix P to capture row swaps is central to these approaches. See partial pivoting and complete pivoting for details, and permutation matrix for the formal object that encodes the swaps.

Computational aspects

Complexity and memory

For dense n-by-n matrices, computing an LU factorization with pivoting generally requires on the order of n^3 operations and stores roughly the same amount of data as the original matrix. Once the factorization is known, solving Ax = b costs about two triangular solves (forward and backward substitution) plus a few vector operations, which is O(n^2) per right-hand side. See Gaussian elimination for the computational lineage and complexity discussions in numerical linear algebra.

Sparse LU factorization

When A is sparse, naive LU can destroy sparsity (fill-in), turning a sparse problem into a dense one. Specialized sparse LU algorithms aim to limit fill-in through reordering and structure-aware techniques. This is crucial for large-scale applications in engineering and scientific computing. See sparse matrix and fill-in for related concepts.

Numerical stability

Pivoting improves stability by avoiding divisions by tiny numbers and by controlling error growth. Nonetheless, the conditioning of A ultimately governs the sensitivity of the solution to perturbations. In ill-conditioned problems, LU factorization may be supplemented by refinement techniques or alternative methods. See conditioning (numerical analysis) for a deeper treatment.

Variants and related factorizations

  • Doolittle method: L has unit diagonal, U is general upper triangular. See Doolittle method.
  • Crout method: U has unit diagonal, L is general lower triangular. See Crout method.
  • LDU decomposition: A = LDU with L and U triangular (L lower, D diagonal, U upper); helps separate diagonal scaling from triangular structure.
  • PLUQ and related factorizations: Incorporate both row and column permutations to handle broader classes of matrices. See PLUQ decomposition.
  • Relationship to other methods: LU factorization is a direct-method alternative to QR for solving linear systems in certain settings and serves as a building block for computing inverses and determinants. See QR decomposition and inversion of a matrix for context.

Applications and limitations

  • Direct solution of linear systems: After A is decomposed, multiple right-hand sides can be handled efficiently via forward/backward substitution. See linear system for broader context.
  • Determinants and inverses: The determinant of A, when LU is available, is the product of the diagonals of U (times a sign from pivot permutations). See determinant and inverse of a matrix.
  • Stability considerations: While pivoting improves robustness, the overall accuracy hinges on the conditioning of A. In some ill-conditioned cases, alternative approaches or reformulations (e.g., regularization, QR decomposition) may be preferable. See conditioning and numerical stability.
  • Applications to sparse systems: Sparse LU factorization is a major area in scientific computing, balancing fill-in against the need to preserve sparsity for efficiency. See sparse matrix and fill-in.

See also