LU Decomposition
LU decomposition factors a matrix A into the product of a lower-triangular L and an upper-triangular U, A=LU, accelerating repeated linear solves.
Purpose
To pre-factor once and then efficiently solve linear systems with multiple right-hand sides.
Mechanism
It is the matrix form of Gaussian elimination: the elimination process yields L (the multipliers) and U (the eliminated result). Solving Ax=b becomes Ly=b (forward substitution) then Ux=y (back substitution). Decomposition costs O(n^3); each solve costs O(n^2).
Use cases
- Linear system solving
- Matrix inversion
- Numerical linear algebra