LU Decomposition

Definition

The LU decomposition of a matrix $\mathrm{A}$ is a factorization $\mathrm{A}=\mathrm{LU}$, where $\mathrm{L}$ is unit lower-triangular (ones on the diagonal) and $\mathrm{U}$ is upper-triangular.

Intuition

Gaussian elimination simultaneously produces two matrices: the upper-triangular result $\mathrm{U}$ and the record of elimination multipliers $\mathrm{L}$. LU decomposition simply names and stores both, amortising the $O(n^3)$ elimination cost across all future solves with the same $\mathrm{A}$.

Formal Description

From Elementary Matrices, Gaussian elimination gives

$${\mathrm{M}}_3{\mathrm{M}}_2{\mathrm{M}}_1\mathrm{A}=\mathrm{U}⟹\mathrm{A}={\mathrm{M}}_1^{-1}{\mathrm{M}}_2^{-1}{\mathrm{M}}_3^{-1}\mathrm{U}=LU.$$

Inverting each elementary matrix simply negates the off-diagonal multiplier:

$${\mathrm{M}}_1^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right),{\mathrm{M}}_2^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -1& 0& 1\end{array}\right),{\mathrm{M}}_3^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}\right).$$

The lower-triangular factor $\mathrm{L}={\mathrm{M}}_1^{-1}{\mathrm{M}}_2^{-1}{\mathrm{M}}_3^{-1}$ is assembled by simply placing the elimination multipliers into their respective positions:

$$\mathrm{L}=\left(\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ -1& 1& 1\end{array}\right).$$

The full decomposition for the example matrix is:

$$\left(\begin{array}{ccc}-3& 2& -1\\ 6& -6& 7\\ 3& -4& 4\end{array}\right)=\left(\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ -1& 1& 1\end{array}\right)\left(\begin{array}{ccc}-3& 2& -1\\ 0& -2& 5\\ 0& 0& -2\end{array}\right).$$

The off-diagonal entries of $\mathrm{L}$ are exactly the elimination multipliers used during Gaussian elimination. LU decomposition requires $O(n^3)$ operations; once computed, each solve $\mathrm{Ax}=\mathrm{b}$ costs only $O(n^2)$.

Applications

Solving $\mathrm{Ax}=\mathrm{b}$ for many vectors $\mathrm{b}$ — see Solving (LU)x=b. Also used internally for determinant computation and matrix inversion.

Trade-offs

• Requires $\mathrm{A}$ to be non-singular (or at minimum that no zero pivot is encountered without row swaps); a singular matrix has no LU factorisation without permutation.
• Without pivoting the decomposition exists only if no pivot is zero; partial pivoting (producing $\mathrm{PA}=\mathrm{LU}$) is required for general non-singular matrices.
• Storing both $\mathrm{L}$ and $\mathrm{U}$ uses $O(n^2)$ memory, the same as $\mathrm{A}$ itself (they can be packed into a single matrix).

Links

• Elementary Matrices
• Gaussian Elimination
• Solving (LU)x=b