4.3 Pivoting Strategies

If Gaussian elimination were only a matter of subtracting multiples of rows, life would be simple. But the reality is more fragile: every division step introduces the possibility of amplifying errors. Every subtraction risks catastrophic cancellation. Every “pivot” — the number we divide by — determines how stable or unstable the entire computation will be.

In other words, elimination does not fail because the method is wrong. It fails because we choose the wrong pivots.

This makes pivoting one of the most critical concepts in numerical linear algebra. It is as central to elimination as lane discipline is to driving. Without it, the algorithm may still technically “work,” but the results may be dangerously unreliable.

What Is a Pivot?

At each elimination step, we divide by a specific number — the diagonal element at that moment in the algorithm. This number is the pivot.

The pivot should ideally be:

• large enough to avoid huge multipliers
• representative of the column (not a numerical outlier)
• stable under floating-point arithmetic

But Gaussian elimination, taken literally, simply uses the entry that happens to be there: the current diagonal element. If that entry is tiny — real tiny — the next operations can blow up numerically.

This is why pivoting exists. Pivoting chooses better pivots.

Why Bad Pivots Break Everything

Let’s imagine a pivot that is extremely small, say 1e-12. During elimination, we divide by this pivot to form the multiplier for the next row operation. This multiplier might be:

m = a_ji / pivot

If the numerator a_ji is anywhere near 1, then m might be on the order of 1e12. Now every subtraction step looks like:

row_j = row_j - (1e12) * row_i

This does not merely “update" the matrix — it destroys it. Huge multipliers magnify rounding errors. Large intermediate values cause overflow. Nearly equal values get subtracted, causing catastrophic cancellation.

A bad pivot is like building a skyscraper on wet sand.

Pivoting replaces the sand with something firmer.

Types of Pivoting

There are three broad classes of pivoting strategies used in practice:

1. Partial Pivoting
2. Complete Pivoting
3. Scaled Pivoting

Each has its own philosophy, cost, and purpose.

1. Partial Pivoting (The Practical Standard)

In partial pivoting, at each step we look down the current column and select the largest absolute value as the pivot. Then we swap rows so that this element moves to the diagonal.

This is also known as:
LU decomposition with partial pivoting → PA = LU

Why do we choose the largest absolute value?

• It maximizes the magnitude of the pivot.
• This minimizes the multipliers m = a_ji / pivot.
• Small multipliers → less rounding error → more stable elimination.

Partial pivoting is used in LAPACK, NumPy, MATLAB, and most production solvers because:

• It offers very strong numerical stability.
• It is computationally cheap — only row swaps.
• It works extremely well in real-world problems.

In practice, partial pivoting is enough for almost every engineering or scientific application.

2. Complete Pivoting (Maximum Safety)

Complete pivoting goes further: Instead of searching just the current column, it searches the entire remaining submatrix.

Then it:

• swaps rows,
• swaps columns,
• and uses the largest absolute value in the entire region as the pivot.

This seems like a clear improvement — and theoretically, it is. Complete pivoting guarantees even stronger bounds on numerical error.

But there is a catch:

Complete pivoting is too expensive for real systems.

Column swaps complicate memory layout, destroy sparsity patterns, and cost far more than the gains they offer. So while complete pivoting appears in textbooks, it rarely appears in production code.

3. Scaled Pivoting (When Numbers Differ Wildly)

In scaled pivoting, each candidate pivot is judged by a ratio:

|a_ji| / (maximum absolute value in row j)

This guards against a situation where:

• a row has extremely large values
• but the pivot candidate is tiny in relative terms

Scaled pivoting is a compromise between robustness and cost, and is useful when data magnitude varies dramatically between rows.

Pivoting as Stability Insurance

At its core, pivoting is about survival in floating-point arithmetic. Real matrices are messy — they contain:

• naturally tiny values
• spuriously tiny values due to cancellations
• large dynamic range across rows or columns

Elimination without pivoting pretends none of this matters. Pivoting acknowledges that it does — and protects the computation accordingly.

Without pivoting, LU decomposition may produce:

• huge multipliers
• ill-conditioned intermediate matrices
• catastrophic error amplification
• division by values indistinguishable from zero

With pivoting, elimination becomes stable enough that LU is trusted inside:

• optimization solvers
• deep learning frameworks
• simulation engines
• probabilistic inference
• scientific and engineering libraries

The difference is not subtle — it is the difference between reliable computation and unpredictable behavior.

Transition to 4.4 When Elimination Fails

Pivoting is powerful, but it is not a magic shield. There are matrices for which even the best pivoting strategy struggles — matrices that hide zero pivots, amplify errors, or break down structurally during elimination.

To understand these “difficult” cases — and why sometimes elimination simply cannot proceed — we turn next to:

4.4 When Elimination Fails