the Thomas algorithm
/ TOM-as /
Many problems give you a matrix that is almost entirely zeros, with nonzeros only on the main diagonal and the two diagonals immediately next to it — a tridiagonal matrix. This shape shows up whenever each unknown couples only to its immediate neighbours, as in a 1D heat equation or a cubic spline. The Thomas algorithm is the specialized, blazingly fast version of Gaussian elimination for exactly this structure.
It is just elimination that ignores all the structural zeros. Sweeping forward, each row's elimination touches only the single entry below the diagonal, so the whole forward elimination is a short loop that updates the diagonal and right-hand side in place; then a back-substitution sweep recovers the unknowns from bottom to top. Because there is only a constant amount of arithmetic per row, the entire solve costs O(n) flops and O(n) storage — linear, not the O(n^3) and O(n^2) of a dense solve. For a million-unknown tridiagonal system that is the difference between instant and impossible.
The Thomas algorithm is the model case of exploiting sparsity: when a matrix has a known thin structure, you tailor the elimination to it and the cost collapses dramatically. It generalizes to banded matrices (a few diagonals wide) with cost O(n b^2) for bandwidth b. Two honest caveats: like plain Gaussian elimination it does no pivoting, so it can be unstable in general — but it is provably stable for the common cases of diagonally dominant or symmetric positive-definite tridiagonal matrices, which is most of what arises in practice; and if any pivot becomes zero or tiny without those guarantees, you must fall back to a pivoting solver.
A 1D Poisson discretization gives a tridiagonal matrix with 2 on the diagonal and -1 next to it; Thomas solves the n-unknown system in about 8n flops instead of the ~2n^3/3 a dense LU would cost.
Linear cost from a thin band: the structural zeros are never even visited.
The Thomas algorithm does no pivoting, so it is not unconditionally stable; it is safe for diagonally dominant or symmetric positive-definite tridiagonal systems (the usual cases) but can fail otherwise.