Pivoting — where it appears
Named by 8 essays across 2 fields — each of them below, with the objects they name alongside it.
A rule that is correct and unusable
Cramer's rule gives every component of the solution in closed form, in terms of determinants, and it is a theorem. On two-by-two systems whose rows are nearly parallel it returns an answer with a backward error of 458 units of roundoff where elimination returns 1.3 — on a matrix whose condition number is 32,000 and which elimination solved perfectly.
Which of the choices is doing the work
Elimination makes n − 1 decisions and they are not worth the same. On 8×8 standard normal matrices, removing the first pivot search and leaving the other six multiplies the median growth factor by 1.624; removing the last multiplies it by 1.000. The cost falls monotonically along the run, and the worst single matrix in the sweep grows by 2,366 when one early decision goes — so the median is the wrong statistic and the tail is where pivoting earns its reputation.
The order the greedy rule cannot choose
Wilkinson's matrix is the standard demonstration that partial pivoting's growth bound of 2^(n−1) is attained. It is attained by the row order the greedy rule picks, and not by the matrix: a single cyclic shift of the rows gives growth 2 at every size, with no multiplier above one. At n = 7 that is 64 against 2. And perturbing one entry by 10⁻¹² leaves the good order exactly where it was while putting every tie-break of the greedy rule back on 64.
One step ahead is one step short
Partial pivoting takes the largest entry in the column and, on Wilkinson's matrix, walks into growth of 2^(n−1) that a cyclic shift of the rows avoids entirely. A rule that chose instead the pivot whose elimination leaves the smallest trailing submatrix was expected to see the good order at the first step. It sees nothing there: every first pivot leaves a largest entry of exactly 2, and with the ties broken by 10⁻¹² it prefers the greedy row by 10⁻¹². It attains 2^(n−1) at every size. Looking two eliminations ahead, the greedy row scores 4 and every other row 2, and the growth is 2 at every size up to 24. On random matrices one step of look-ahead helps below n = 16 and is worse than greedy on more than half of them by n = 32.
A doubling that arrives two steps late
A pivot rule that looks one elimination ahead chooses Wilkinson's growth row for row, because the doubling it sets up arrives one step later; looking two ahead escapes it. The argument said a matrix whose damage arrives two steps late would defeat the two-step rule the same way. It exists, and it is two Wilkinson matrices interleaved: W ⊗ I₂. Every look-ahead of depth one or two reproduces the greedy rule's growth on it exactly, 4 to 64 from n = 6 to 14, and depth three gives 2. Three copies defeat depth three and yield to four. The growth each depth is held to is 2^(n/d − 1): a fixed depth stretches the exponential and never removes it, at a cost that rises by a factor of about n for every step it looks.
The baseline was the interchanges
Small pivots along grid rows gave a fixed fill-reducing plan twice the saving over the natural order that scattered ones did, for a factor of the same size, and the reading was that the natural order did badly on rows. Turning the lines to run along columns was predicted to bring the natural order below 1,000 entries, leave the plan within 3 per cent of 907, and drop the saving to the scatter's. It misses on all three: 1,008, 977 and 3.1 per cent. What the natural order paid for on rows was its own interchanges. Offered by position, as a dense code offers it, every Bunch–Kaufman interchange moves a row out of sequence, and on rows that costs 125 entries at three in ten and 191 at half — the most of any layout at every share. Kept to the grid's index, the natural order barely notices the layout, and the row lines' saving halves to 9.0 per cent.
A definite pivot sits at the mean
On a positive-definite matrix every Cholesky pivot is at or above the smallest eigenvalue, so a shift read off the smallest pivot always has to be pushed down, and it was predicted to need a median of four pushes and to be usable unpushed on none. The second half holds on all ninety matrices measured. The first does not: shrinking by a quarter at a time takes a median of six to ten steps, because the smallest pivot sits within a factor of two of the spectrum's harmonic mean, and the harmonic mean sits four to nine times above the smallest eigenvalue. The push was a device for the indefinite case, which has no floor to aim at. A definite matrix does, and halving towards zero gets below the spectrum in a median of two to four.
A vertex, not an order
A definite matrix's smallest Cholesky pivot sits at the harmonic mean of its spectrum, and the prediction was that a localised bottom would change that for the pivoted factorisation alone: on a path with one weak edge, taking the largest diagonal first would land within a factor of 1.2 of the smallest eigenvalue while the unpivoted pivot stayed at the mean. On the prediction's own family neither rule comes within a factor of three, because a weak edge does not localise the bottom on a vertex — it splits it over the shorter piece, and the best pivot any order can reach is the smallest eigenvalue times that piece's length. Where the bottom really does sit on one vertex, both rules land within two per cent, the unpivoted one wherever in the order that vertex happens to fall. The pivot counts the vertices the bottom lives on; the order chooses nothing.
Named alongside it
The objects these essays reach for when they reach for this one.
LU factorisationGaussian eliminationGrowth factorPartial pivotingBackward errorCombinatorial searchExact ground truthPermutationBunch–KaufmanCholesky factorisationFlop countInertia