LUdekomposition

LU dekomposition, also known as LU decomposition, is a factorization of a square matrix A into the product of a lower triangular matrix L and an upper triangular matrix U. In many formulations a permutation matrix P is included to account for row exchanges, giving PA = LU. When L is constrained to have unit diagonal, the form is often called the Doolittle decomposition; if U is constrained to have unit diagonal, it is referred to as the Crout form.

Existence and variants: An LU decomposition with partial pivoting (PA = LU) exists for all square matrices that can be factored without division by zero during elimination, and it is widely used because partial pivoting improves numerical stability. Some matrices require row permutations to avoid zero pivots; without pivoting, LU factorization may fail even if A is invertible.

Computation: LU factors are obtained via Gaussian elimination. The multipliers used at each elimination step form the strictly lower triangular part of L, while the resulting upper triangular part becomes U. In practice, L and U are often stored in the same memory block as A for space efficiency.

Applications: The primary use is solving linear systems A x = b by forward and backward substitution. If PA = LU, one solves L y = P b for y, then U x = y for x. LU decomposition also facilitates computation of determinants (det(A) = det(P) det(L) det(U) with det(L) = 1 if L has unit diagonal), and matrix inversion or condition estimation.

Numerical considerations: Partial pivoting provides better numerical stability. The typical computational cost is O(n^3) operations for an n×n matrix, and the factorization can be performed in place, using O(n^2) extra storage.