Which of the choices is doing the work

Elimination is a sequence of choices argued that Gaussian elimination is taught as a procedure with no decisions in it, that there is one decision at every step — which row to use — and that every stability property the algorithm has comes from making that decision well. The argument is correct and it is not specific. Seven decisions are made on an 8×8 matrix, and if the stability comes from making them well, some of them must be carrying more of it than others.

There is a way to ask which. Remove exactly one decision — at step k take the first row still available instead of the largest — leave the other six searches in place, and compare the growth factor to the fully pivoted one. That is seven separate algorithms, each differing from partial pivoting in one place.

The cost falls along the run #

Over sixty standard normal 8×8 matrices, whose median growth factor under full partial pivoting is 1.342, removing one decision multiplies that median by

The ordering is monotone and it is not subtle: the first decision is worth twenty-five times as much as the fifth and the last is worth nothing at all on the median matrix.

Two things produce that shape and they are separable. The first is arithmetic: a bad pivot at step k contaminates the trailing (n − k)×(n − k) submatrix, and the growth it introduces has n − k − 1 further steps in which to compound. A bad choice at step 7 of 7 leaves a 1×1 submatrix behind and there is nothing left for it to spoil.

The second is combinatorial and is the other bar in the figure. At step k there are n − k rows to choose from, so the probability that the largest is not already in place is 1 − 1/(n − k), which falls from 7/8 at the first step to 1/2 at the last. Measured: the search moves a row on 90, 87, 88, 80, 75, 80 and 43 per cent of these matrices. The last decision costs nothing partly because it is usually not a decision.

And no single one of them is the algorithm #

The more interesting number is the largest, and it is 1.624. Removing the single most valuable pivot decision that partial pivoting makes, on a random 8×8, multiplies the growth factor by about five eighths on the median matrix.

That is a small number for something the whole apparatus is built around, and it is the finding. Partial pivoting’s stability is not a property of any one of its decisions. It is a property of all of them together, and the reason is that the quantity being bounded is a product: the growth factor accumulates over steps, each multiplier is held at or below one by the search at its own step, and removing one of those bounds leaves the other six in place. What a single removed search costs is one unbounded multiplier’s worth, and one is not many.

The shape does not change with the size. At n = 12 there are eleven decisions, the first is again the dearest, and none of them individually multiplies the median growth by three.

The same figure says something about the shape of the search that is easy to miss. The bar for how often a decision moves a row falls much more slowly than the bar for what the decision is worth: 90 per cent down to 43 per cent, against 1.624 down to 1.000. So the late searches are still doing work — they are still changing the row used at four steps in ten — and what they change has stopped mattering. A pivot search that reported how often it moved a row would report an algorithm working hard throughout, and the reporting would be true and would say nothing about where the stability came from.

Where the reputation comes from #

None of which means partial pivoting is not worth its cost, and the median is exactly the statistic that would leave that impression. The worst matrix in each column of the sweep is the other story.

Removing the step-2 search costs the median matrix a factor of 1.545 and costs the worst matrix of sixty a factor of 2,366. Step 1’s worst is 190, step 4’s is 99, step 6’s is 76. The distribution is not concentrated around its median at all: most matrices do not care which row is used at any given step, and a few care enormously.

That is the shape every argument for pivoting has always had, and it is worth seeing as a distribution rather than as an anecdote. The bound that is never attained is the same observation about the growth factor itself — a bound of $2^{n-1}$ that random matrices come nowhere near and that a constructed matrix attains exactly, and a bound that holds with probability is the same quantity given a distribution rather than a worst case. Here it is one level down, about the decisions rather than about the outcome: the median decision is not worth making and the tail decision is worth everything, and nothing in the matrix says in advance which kind of decision the next step holds.

The 2×2 with a tiny leading entry is the extreme case of that distribution with n − 1 = 1, which is why it is the example everybody uses and why it is misleading about the general case. It has exactly one decision, so that decision carries all of the stability by construction, and the intuition it leaves — that the first pivot is the one that matters — is the intuition the sweep above refuses.

A threshold between fill and growth is the same distribution seen from the sparse side, where a swap costs fill and the question is how much growth to accept in exchange. The sweep here prices the two ends of that trade on dense matrices: a search kept is worth 1.624 on the median matrix at the step where it is worth most, and a search dropped costs 2,366 on the worst of sixty. A threshold rule is a bet that the matrix in hand is a median one.

What a search costs, against what it is worth #

The pivot search is not free and the arithmetic is worth putting beside the measurement. At step k it compares n − k entries, so the whole of partial pivoting’s searching is n(n−1)/2 comparisons against the elimination’s own $n^3/3$ multiply-adds — about 3/(2n) of the work, which is 19 per cent at n = 8 and 2 per cent at n = 100.

The searches that cost the most are the early ones, which is the same end of the run where they are worth the most: step 1 compares n entries and is worth 1.624, step n − 1 compares two and is worth 1.000. So the value and the price are aligned, which is a convenient accident rather than a design, and it means a partial search — pivoting only for the first half of the steps — keeps most of the benefit for a quarter of the comparisons.

That is a measurable claim and it is not made here: skipping one decision is not skipping several, and the compounding argument above says the cost of skipping a run of them should be worse than the product of the individual costs rather than equal to it. Which it is, is the direct continuation.

The decision that is not a decision #

Forty-three per cent at the last step is the one number in the table that is a statement about the problem rather than about the algorithm, and it deserves its own reading.

At step n − 1 there are two rows left and the search compares two entries. If they were independent draws from a symmetric distribution the largest would be the first half the time, so a rule that always searched would move a row half the time — and 43 per cent is close enough to a half that the small shortfall is the only interesting part. The rows at step n − 1 are not independent: they are what six eliminations have left of two rows that started independent, and the eliminations have been driven by the same pivots, so the remaining entries share a history.

Whatever produces the shortfall, the practical reading is that the last search is a coin toss whose outcome does not matter, and the last three searches on an 8×8 together are worth 1.058 on the median matrix. A code that stopped pivoting for the final third of the run would be making a defensible trade on a random matrix and an indefensible one on any matrix whose difficulty is at the end — which includes every matrix whose trailing submatrix has a small pivot in it, which is most of the structured ones.

The pivot that reads the units is the standing warning about that class of shortcut: a rule that is right about a matrix in one set of units is wrong about the same matrix in another, and “the last searches do not matter” is a statement about magnitudes that a change of units moves.

What the removed decision actually does #

It is worth being exact about what “remove the decision” means, because there are two ways to remove it and they are not the same.

The variant measured takes the first row still available — which is what no pivoting does, and what a code with the pivot search deleted would do. The other variant would take a row at random, which is a different and weaker statement: a random row is usually not the worst row, and the first available row is the one the matrix’s own ordering put there, which on a matrix constructed to be difficult is exactly the wrong one.

So the numbers above are the cost of deleting the search, not the cost of choosing badly. On a standard normal matrix the two coincide, because the row that happens to be first is a random row. On Wilkinson’s matrix they do not, and the next essay is about a case where taking the first available row is better than taking the largest.

A pivot that searches one row and one column is the opposite direction — a larger search than partial pivoting’s, priced against what it buys — and the two measurements bracket the same question from either side. Rook pivoting looks at more entries and finds a pivot no column search could; deleting a column search looks at fewer and loses one multiplier’s bound. The sweep here says the second loss is small on a random matrix, which is the same reason the first gain is small on one.

What must fail for any of this to be wrong #

Three things, each fed input it must refuse. That the first decision moves a row on most matrices — at 90 per cent it does, and a claim that the search is usually idle fails. That removing the costliest single decision multiplies the median growth by less than three — it multiplies it by 1.624, and a claim that some one step’s removal costs more than tenfold fails. And that the last decision is cheaper than the worst, which is the monotonicity the whole shape rests on.

The growth factors are computed by one routine that takes an explicit row order, so the fully pivoted elimination and the six one-decision-removed ones are scored by the same arithmetic rather than by seven variants of it. That matters more than it sounds: the natural way to write this is to copy the elimination loop and edit one line, and seven copies of an elimination loop is seven chances for the comparison to be between implementations rather than between orders.

Why the median and the worst disagree so much #

The gap between 1.624 and 2,366 is four orders of magnitude, on the same seventh of the same experiment, and it is worth saying why a growth factor should have a distribution of that shape.

Growth under partial pivoting is a product of per-step factors each bounded by two, and the bound is attained only when a whole column of the trailing submatrix has entries of equal magnitude and opposite sign — a coincidence that a random matrix does not produce and that accumulates multiplicatively when it does. So the distribution of growth is the distribution of a product of mostly-near-one factors with an occasional large one, which is lognormal-ish with a heavy right tail, and the median of such a thing says almost nothing about its maximum.

Removing a pivot search removes the bound on one of those factors. On a matrix where that factor was going to be near one anyway, nothing happens; on a matrix where the entry the search would have rejected is tiny, that factor becomes 1/ε for whatever small ε was sitting there, and the rest of the product carries it. Sixty matrices is enough to see the median settle and is not enough to see how far the tail goes — the 2,366 is the largest of sixty and is a lower bound on nothing in particular.

That asymmetry is the practical argument for the search and it is not the argument the median makes. Pivoting is insurance: on almost every matrix the premium buys nothing, and the reason to pay it is that the loss it prevents is unbounded and the premium is 3/(2n) of the work.

What this does not settle #

Sixty matrices at each size, standard normal, at n = 8 and n = 12. Standard normal matrices have growth factors near one and are the easy case for every pivoting question; nothing here says what the same sweep does on a matrix family with structure in it.

One decision removed at a time, never two. The compounding argument predicts that removing a run of k consecutive searches costs more than the product of their individual costs, and that is unmeasured.

The measure is the growth factor and not the backward error. They are related by a factor involving n and the unit roundoff, and the relation is an inequality rather than an identity — a large growth factor permits a large backward error and does not produce one. The bound that is never attained is about that gap and this essay inherits it.

And the removed search is replaced by the first available row rather than by anything adversarial, so every number above is a statement about matrices whose row order carries no information.

Still open: runs of decisions, and a search that stops early #

Skipping several. The whole shape above says the cost of a removed search is one unbounded multiplier. Removing two adjacent searches should cost more than 1.624 × 1.545 if the growth compounds and about that if it does not, and which it is would say whether the decisions interact or merely accumulate.

A search with a threshold. Threshold pivoting takes the diagonal entry whenever it is within a factor τ of the largest, which is a partial search rather than no search, and it is what every sparse code ships because a swap costs fill. The sweep here is the τ = ∞ and τ = 0 ends of that family, and the shape of the curve between them — whether most of the 1.624 is recovered at τ = 10, or only at τ near one — is the measurement a sparse code would want.

The same sweep on a family that grows. Every matrix here has a growth factor near 1.3, so the measurement is of decisions that barely matter on matrices that barely need them. On the shooting matrices, whose growth is exponential in the number of steps, the same seven-column table would say whether the damage is concentrated in the steps where the transfer matrix is expanding — and would be a statement about which decisions a structured matrix makes load-bearing.