= LU decomposition
{c}
{title2=$A=LU$}
{wiki}
= LU factorization
{c}
{synonym}
An <LU decomposition> writes a <square matrix> as $A=LU$, with $L$ a <lower triangular matrix> and $U$ an <upper triangular matrix>. We use a <unit triangular matrix> $L$, meaning $l_{ii}=1$. The factors record <Gaussian elimination>: $U$ contains the reduced equations, while $L$ stores the <elimination multipliers> needed to reconstruct the original equations. This makes <Reusing LU factors for multiple right-hand sides> inexpensive.<Fundamentals of Numerical Computation by Tobin A. Driscoll and others>[§2.4.3, Definition 2.4.2 and equation (2.4.7): unit lower triangular L and upper triangular U]{ref}
For an <invertible matrix>, unpivoted <LU decomposition> requires nonzero <pivot elements> at every elimination step; invertibility alone does not guarantee this. In general use <Pivoted LU decomposition>, with the explicit convention $PA=LU$ and a <permutation matrix> $P$. Once the factors exist, solving a <linear system> $Ax=b$ needs <forward substitution> followed by <back substitution>, rather than forming a <matrix inverse>.
Back to article page
