Partial pivoting — where it appears
Named by 25 essays across 4 fields — each of them below, with the objects they name alongside it.
Elimination is a sequence of choices
Gaussian elimination is taught as a procedure with no decisions in it. There is one decision at every step — which row to use — and every stability property the algorithm has comes from making it well.
The swap that is not optional
Run elimination without a row interchange on a matrix that needs one and nothing announces a failure. There is no division by zero, no warning, and an answer of the right shape. It is simply wrong, and how wrong depends on a number you did not look at.
The bound that is never attained
Partial pivoting's stability guarantee permits the entries to double at every step — a factor of 5.5·10¹¹ at n = 40. The measured growth on random matrices of that size is about three. The gap is eleven orders of magnitude, and the guarantee is still worth having.
The pivot that reads the units
Partial pivoting compares the entries of a column and takes the largest. Those entries carry units, so the comparison depends on them — and there is a row scaling, on the standard two-by-two that pivoting exists to fix, which makes partial pivoting perform the identical catastrophic elimination it was introduced to prevent, with no interchange at all.
A factorisation with nothing to pivot for
Cholesky's growth factor is not bounded by one. It is equal to one, at every size and every condition number, and the two-line reason is why the algorithm needs no pivoting at all — not "usually gets away without it". Its only failure is the square root of a non-positive number, which is exactly the test for definiteness, and in floating point that test moves with the precision.
When symmetry is not enough
The matrix [[0, 1], [1, 0]] is symmetric, nonsingular and perfectly conditioned, and there is no diagonal entry to pivot on. Every factorisation restricted to symmetric interchanges and one-by-one pivots fails on it, at any depth of searching, because every entry it could search is zero. The repair is to take two variables at once.
The recursion that was never told the memory
A blocked elimination has to be tuned to its fast memory, and tuned to one memory it costs up to 2.9 times the best at another. A recursive elimination splits the columns in half down to one and reads no memory size at all. On eight fast memories from 36 to 576 words it moves between 0.94 and 1.28 times the words of the best tuned block, with the same 585,200 operations and the same pivots — and on a machine with two caches it beats the block tuned to either cache on six machines of seven.
A pivot that searches one row and one column
Rook pivoting looks down a column for its largest entry, along that entry's row for a larger one, and back down that entry's column, until it finds an entry largest in both. On Gaussian matrices of size 64 it keeps the median growth factor at 2.53 against partial pivoting's 4.06 and complete pivoting's 1.88, and it compares 6,987 entries against 2,080 and 89,440. On Wilkinson's matrix it holds the growth at exactly 2 where partial pivoting reaches 9.2·10¹⁸. And on a matrix built to make it walk it compares 113,376 entries — more than complete pivoting.
A worst case is as fragile as its margin
Wilkinson's matrix grows by 5.5·10¹¹ under partial pivoting, and adding Gaussian noise of 10⁻¹⁴ to every entry takes its median growth to exactly 2. The shooting matrix from a boundary-value problem grows by 1.1·10⁴, and noise ten million times larger leaves it untouched. The difference is what each worst case rests on. Wilkinson's rests on exact ties between candidate pivots, which any noise breaks. The shooting matrix's rests on a choice made by a margin of 5.6·10⁻³, and between 10⁻⁶ and 10⁻³ its median growth is that margin divided by the noise, times a constant between one half and four thirds.
The block size a recursion still has
A recursive elimination is sold as having no block size, and every real one switches to plain loops below some width. Swept over that width, the traffic is a staircase with its steps at the halvings of n, and its cliff sits where the blocked elimination's does — the first panel wider than √M − 2 moves 1.53 to 4.47 times the words, on six memories of six. On three caches the innermost decides, and a third cache costs every tuned block up to 14 per cent and the recursion nothing.
The growth a boundary-value problem supplies
Large growth under partial pivoting is usually said to need a matrix built for it. A two-point boundary-value problem solved by multiple shooting supplies one without being asked: its growth factor is e^(5T/6)/2 to four figures — 1.1·10⁴ at an interval of 12, 1.3·10⁵ at 15 — on a matrix whose condition number never exceeds 8.3, while rook and complete pivoting keep it below 2. And it is the finer shooting grid that grows: below a step of 0.3397 the choice partial pivoting makes turns on one entry against one, and above it there is no growth at all.
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.
Three orders and one last entry
Over the integers there is no stability to pivot for, so a fraction-free elimination swaps rows only when the pivot is zero. Choosing a pivot for length instead does change the sequence of minors — the smallest-nonzero rule makes seven exchanges where the natural order makes none and keeps the profile two bits lower through the middle. It cannot change the peak. The last entry of the elimination is the determinant, and the determinant does not know what order it was computed in.
Noise the growth amplifies
The shooting matrix's growth of 1.1·10⁴ fell under noise as its pivot margin divided by the noise, and the explanation offered was noise reversing partial pivoting's choices. But noise of 10⁻⁵ is five hundred times smaller than that margin. Add the same noise only to the entries that are not zero and every draw keeps the whole growth up to 10⁻³. The dense noise was not reversing the comparisons by itself: it sat in the zeros, the elimination multiplied it by the growth already made, and a comparison flips when that product reaches about four tenths of the margin — at every noise level from 10⁻⁶ to 10⁻³.
A margin the factorisation records
Partial pivoting finds the second-largest candidate in every column it scans, and throws it away. Keep it, divide the gap by the growth reached at that step, and take the smallest over the steps before half the final growth has arrived. That one number, recorded by the factorisation that is already running, predicts the dense noise that halves the growth to within a factor of 0.92 to 2.4 on shooting matrices whose growth runs from 75 to 1.3·10⁵ and whose fragility spans three and a half decades — and on Wilkinson's matrix it is exactly zero.
A threshold that holds the growth still
Partial pivoting's large growth on the shooting matrix rests on a margin of 5.6·10⁻³, and Wilkinson's rests on exact ties, which a perturbation at rounding breaks. A sparse code pivots with a threshold instead, taking the sparsest row among candidates within a factor τ of the largest. At every threshold from 1 to 0.1 both matrices grow by exactly as much as under partial pivoting. But the growth is now held by row counts, which no perturbation of the values can reverse: at τ = 0.1 it survives noise on the stored entries up to 0.56 on the shooting matrix, three hundred times more, and 0.18 on Wilkinson's, where partial pivoting's goes at 10⁻¹⁶. The margin that predicts it is the chosen candidate's height above the threshold line, and it needs no division by the growth.
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.
Leaves cut to the edge on purpose
A recursive elimination's cheapest leaf is exactly the square root of M, less 2, columns wide, and the rule drawn from it was to set the base case there and let the halvings put the leaves at or below it. On thirty-two sizes from 96 to 127 columns, halving to that base case moves more words than the pure recursion on sixteen of them at 144 words of fast memory, because the halvings stop at six and seven columns, not ten. Cut every dimension at a multiple of the edge instead and every size keeps the saving: 0.79 to 0.86 of the pure recursion's words, against halving's 0.91 to 1.07, with the same arithmetic and the same pivots. What it cannot make full is the one leftover leaf, and a leftover of one column is where it loses.
A trigger finer than the growth
Threshold pivoting cannot remove the shooting matrix's growth of 1.1·10⁴, because at τ = 1 it is partial pivoting. The proposal was a factorisation that notices growth on a step and searches as rook pivoting does after it, paying for the stricter search only where growth is made. But no step makes much: the largest one-step rise is exactly the growing mode's rate over one shooting interval, 1.284 at a step of 0.3, and 1.133 at 0.15. A trigger finer than that rate holds the growth at 2.00 for about two thirds of rook's extra search; one coarser never fires. And a trigger fine enough searches as rook on a quarter of an ordinary random matrix's steps.
The short leaf belongs at the bottom
A recursive LU that cuts every dimension at a multiple of the cache's edge moves 14 to 21 per cent fewer words than the pure recursion, except where one leaf per dimension has to be short — and the one-column leftovers cost the most. Moving the short leaf to the top, where it becomes a thin strip of a large product, was predicted to cure that. It makes it worse on all twenty-nine sizes that have a leftover, by up to three hundredths. The measurement that matters more is the edge itself: one column under it the aligned cut keeps most of its saving, one column over it every size costs two and a half to three times the pure recursion. Halving to the same base case barely notices either mistake.
The scale that only moved a pivot
Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.
The switch is read before the solve
Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.
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 doubling is in the row already
Interleave d copies of Wilkinson's matrix and every pivot rule that looks up to d eliminations ahead walks into growth 2^(n/d − 1); escaping costs a look one step deeper, and a deeper look multiplies its trial eliminations. Rook pivoting looks no further than the present step and escapes every one of them — growth exactly 2 at every deferral and every size — for 3.2 times partial pivoting's comparisons whatever the deferral. The doubling a look-ahead hunts for in the future is already visible in the row in front of it. And the leak that was supposed to let the two-step rule escape was placed where no pivot is ever chosen: at every size up to one, it changes nothing.
Named alongside it
The objects these essays reach for when they reach for this one.
Growth factorGaussian eliminationBackward errorLU factorisationComplete pivotingWorst-case analysisFlop countPermutationWilkinson's matrixExact ground truthRook pivotingBlocked algorithm