pivoting

Plain Gaussian elimination divides each row by the pivot — the diagonal entry it is currently working on. Mathematically any nonzero pivot works, but on a computer a tiny pivot is poison: dividing by something close to zero produces huge multipliers, and those huge numbers swamp the rest of the matrix in rounding error. Pivoting is the simple fix: before each elimination step, swap rows so the pivot is as large as possible.

Partial pivoting, the standard choice, scans the current column from the diagonal down and brings the row with the largest-magnitude entry to the top. This guarantees every multiplier has absolute value at most 1, so no entry can grow uncontrollably during a single step. The factorization it produces is PA = LU, where P is the permutation matrix recording the swaps. Complete pivoting also searches across columns for the largest entry in the whole remaining submatrix; it is safer in theory but rarely worth the extra cost.

The deeper point is that pivoting is what makes Gaussian elimination trustworthy. Without it, elimination can be catastrophically unstable on perfectly ordinary matrices; with partial pivoting it becomes backward stable in practice for essentially all matrices you meet. The cost is only the bookkeeping of row swaps — negligible compared to the arithmetic.

A caveat worth knowing: partial pivoting is stable in practice but not provably so in the worst case. Contrived matrices exist where element growth is exponential. They almost never arise in real applications, which is why partial pivoting remains the universal default while complete pivoting is reserved for the truly paranoid.