LU Decomposition and Efficient Solving

LU decomposition factors a matrix as $PA = LU$, where $P$ is a permutation matrix (from row swaps), $L$ is unit lower triangular (the elimination multipliers on and below the diagonal), and $U$ is upper triangular (the echelon form).

Why is this useful? To solve $A\mathbf{x} = \mathbf{b}$: compute $\ mathbf{c} = P\mathbf{b}$ (apply row permutations, $O(n)$), then solve $L\mathbf{y} = \mathbf{c}$ by forward substitution ($O(n^2)$), then solve $U\mathbf{x} = \mathbf{y}$ by back substitution ($O(n^2)$). Total: $O(n^2)$ per right-hand side after $O(n^3)$ one-time factorization.

This pays off when solving $A\mathbf{x} = \mathbf{b}_1, A\mathbf{x} = \mathbf{b}_2, \ldots$ for many different $\mathbf{b}$: factorize once ($O(n^3)$), then solve each system in $O(n^2)$. MATLAB's $x = A \backslash b$ uses LU under the hood.