JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Direct solvers done right: pivoting, flops, and when to stop

Naive Gaussian elimination is a backward-instability bomb. This guide shows why pivoting defuses it, counts the flops that govern cost, exploits sparsity, and draws the line where direct methods quit and iteration takes over.

Why naive elimination explodes

Gaussian elimination from Vol I divides each row by its pivot. If a pivot is tiny, the multipliers become huge, and huge multipliers magnify the rounding errors already present in the data. The result is a backward-unstable mess: your computed answer solves a problem far from the one you posed. The exact same matrix that elimination handles fine in exact arithmetic can lose every digit in floating point.

Solve  [1e-20, 1; 1, 1] x = [1; 2]   in double precision.
True answer is essentially  x = (1, 1).

NAIVE (pivot = 1e-20):
  multiplier = 1 / 1e-20 = 1e20
  row2 <- row2 - 1e20 * row1
        = [0,  1 - 1e20]  ->  fl gives [0, -1e20]   (the '1' vanished!)
  back-substitute:  x2 = 1,  x1 = (1 - x2)/1e-20 = 0   WRONG

WITH PARTIAL PIVOTING (swap so pivot = 1):
  rows: [1, 1; 1e-20, 1],  multiplier = 1e-20
  row2 <- [0, 1 - 1e-20] = [0, 1]   (no information lost)
  back-substitute:  x2 = 1,  x1 = 1   CORRECT
A 2x2 where naive elimination returns x1 = 0 and pivoting returns the correct x1 = 1.

Partial pivoting: the standard fix

The cure is partial pivoting: before eliminating column k, swap rows so the largest-magnitude entry in that column sits on the diagonal. This forces every multiplier to satisfy |m| <= 1, so they can no longer blow up the errors. Formally it computes a factorization P A = L U, where P records the row swaps and L has unit-bounded entries — the same LU decomposition you met in Vol I, now made safe.

Counting the cost: flops and sparsity

Cost is measured in flops — floating-point operations. LU factorization of a dense n x n matrix costs about (2/3) n^3 flops; each triangular solve afterward is only O(n^2). This asymmetry is why you factor once and reuse: solving for ten different right-hand sides b costs one cubic factorization plus ten cheap quadratic solves, not ten factorizations.

The n^3 wall is brutal: double n and the cost grows eightfold. For the giant systems from discretized PDEs — millions of unknowns — direct factorization is simply impossible. But those matrices are usually sparse: almost all entries are zero. Sparse matrix methods store and operate only on the nonzeros, and the central danger is fill-in: elimination can turn structural zeros into nonzeros, destroying the sparsity. Reordering rows and columns to minimize fill is the whole art of sparse direct solvers.