LU Decomposition

The process of factorizing a square matrix into 2 triangular matrices: a lower triangular matrix ($L$) and an upper triangular matrix ($U$). Introduced by Alan Turing in 1948.

Finding $L$ and $U$ Without Pivoting

Using Gaussian Elimination

Can be used when Gaussian elimination can be performed on $A\vec{x} = \vec{b}$ without row interchanges, $A$ factors as $A = LU$, where

is the multiplier used to eliminate entry $(j, i)$ at step $i$, $U$ is the row-echelon form produced by elimination, and $L$ collects the multipliers:

$L$ and $U$ are produced together in 1 pass of elimination.

• For $i = 1, \ldots, n-1$, use row $i$ as the pivot row.
• For each row $j > i$, compute $m_{ji} = a_{ji}^{(i)} / a_{ii}^{(i)}$.
• Eliminate $a_{ji}$ with $\text{row}_j \leftarrow \text{row}_j - m_{ji} \cdot \text{row}_i$.
• Place $m_{ji}$ at position $(j, i)$ of $L$.

$U$ is the result of elimination. $L$ is the record of multipliers used to produce it.

Direct Computation Method

$L$ and $U$ can also be computed directly by equating entries of $A$ with entries of the product $LU$.

• For $i = 1, \ldots, n$, set $l_{ii} = 1$ or $u_{ii} = 1$.
• Compute $l_{11} u_{11} = a_{11}$.
• For $j = 2, \ldots, n$, compute

• For $i = 2, \ldots, n-1$:
  • Compute $l_{ii} u_{ii} = a_{ii} - \sum_{k=1}^{i-1} l_{ik} u_{ki}$.
    • $a_{ii}$
      Diagonal entry of $A$ at row $i$.
    • $\sum_{k=1}^{i-1} l_{ik} u_{ki}$
      Contribution already accounted for by the first $i-1$ rows and columns of $L$ and $U$.
    • $l_{ii} u_{ii}$
      Remainder left for the diagonal entries of $L$ and $U$ at step $i$, split by the fixed value from step 1.
  • For $j = i+1, \ldots, n$, compute

Pivoting

LU decomposition can fail when the top-left entry of $A$ is $0$ or small compared to other entries.

Pivoting rearranges the rows and/or columns of $A$ to place a larger element in the top-left position, mitigating this. Multiple pivoting algorithms exist.

Applications

• Solving $A\vec{x} = \vec{b}$, used for finding current in a circuit and solving discrete dynamical systems.
• Finding the inverse of a matrix.
• Finding the determinant of a matrix.

Applicable whenever a problem can be modeled in matrix form, since triangular matrices are easy to compute with.

Solving $A\vec{x} = \vec{b}$

Suppose $A = LU$ and $A\vec{x} = LU\vec{x} = \vec{b}$ must be solved.

• Set $\vec{w} = U\vec{x}$.
• Solve $L\vec{w} = \vec{b}$ for $\vec{w}$ by forward substitution, since $L$ is lower triangular.
• Solve $U\vec{x} = \vec{w}$ for $\vec{x}$ by back substitution, since $U$ is upper triangular. This $\vec{x}$ solves the original system.

This uses $L$ to perform row operations on $U$ to solve the system.