Mathematics
Using LU Factorization to Efficiently Solve Systems of Equations
Quick fact
Once the LU factorization is computed, solving a new right-hand side costs only O(n²) time, versus O(n³) for Gaussian elimination from scratch—a massive speedup for large systems and repeated solves.
Why this is interesting
You've solved equations by elimination, but what if you need to solve hundreds of systems with the same matrix? LU factorization is the hidden shortcut that makes this instant work.
Read the full explanation
Understanding Using LU Factorization to Efficiently Solve Systems of Equations
Think of LU factorization as writing a matrix A as the product of two special matrices: L (lower triangular, with zeros above the diagonal) and U (upper triangular, with zeros below the diagonal). Triangular matrices are easy to handle because solving a system with a triangular matrix is straightforward: you just substitute values from one end to the other. Take a simple 2x2 example: if A = [[2, 1], [4, 3]], you can factor it as L = [[1, 0], [2, 1]] and U = [[2, 1], [0, 1]]. Now, to solve A x = b, you first solve L y = b (forward substitution) and then U x = y (back substitution). Both steps are quick because each equation has only one unknown at a time. This factorization is essentially recording the steps of Gaussian elimination: the multipliers you use to zero out entries go into L, and the resulting upper triangular matrix is U. Instead of performing elimination every time, you reuse the same L and U for any new b.
A deeper explanation
The power of LU factorization lies in separating the cost of processing the coefficient matrix A from the cost of handling the right-hand side b. Gaussian elimination, or solving A x = b directly, costs about O(n³) operations (where n is the number of equations). LU factorization also costs O(n³) once, but once you have L and U, solving for a new b only costs O(n²) because you just do two triangular solves. This is why LU factorization is the workhorse in many applications: engineering simulations, economics models, and scientific computing often need to solve the same system with many different right-hand sides (e.g., different loads, different initial conditions). Computing a matrix inverse is an even worse alternative because it requires solving n systems (one for each column of the identity matrix) and is numerically less stable. LU factorization also enables efficient computation of determinants (the product of U's diagonal entries) and is the foundation for more advanced methods like Cholesky decomposition for symmetric positive-definite matrices. In practice, partial pivoting is used to ensure numerical stability by swapping rows so the largest possible pivot is used. This adds a permutation matrix P, giving the factorization P A = L U, but the efficiency benefit remains.