Pivoting Strategies

Pivoting reorders rows or columns during elimination to avoid tiny pivots, keeping multipliers bounded and the factorization numerically stable.

Why pivots matter

During Gaussian elimination, each step divides by a pivot element. A zero pivot stops the algorithm; a very small pivot produces large multipliers that amplify rounding error and can destroy accuracy. Pivoting reorders the matrix so that a well-sized element sits in the pivot position at each step.

Partial pivoting

Partial pivoting searches the current column for its largest-magnitude entry and swaps that row into the pivot position. This keeps every multiplier at most 1 in magnitude and makes elimination backward stable for the vast majority of matrices. It is the default in essentially all production LU routines because it costs little.

Complete and rook pivoting

Complete pivoting searches the whole remaining submatrix and swaps both rows and columns, giving the strongest stability guarantee but at higher search cost and with column permutations to track. Rook pivoting is a compromise. In practice partial pivoting almost always suffices; the rare matrices that defeat it are pathological.

import numpy as np
# without pivoting a tiny leading pivot loses accuracy
A = np.array([[1e-16, 1.0],[1.0, 1.0]])
b = np.array([1.0, 2.0])
print(np.linalg.solve(A, b))   # solved stably with pivoting

Sparse trade-offs

For sparse matrices, pivoting for stability competes with pivoting to minimize fill-in. Sparse direct solvers balance the two, sometimes accepting a slightly less stable pivot to preserve sparsity, using threshold pivoting that allows any pivot within a factor of the largest.

Stable pivoting underlies the dense subsolves and preconditioner factorizations used within the larger sparse solvers of breeder Hyperion simulations.