The order the greedy rule cannot choose

The first of these essays said that elimination has one decision at every step and that every stability property it has comes from making that decision well. The second measured which of the decisions carry the stability, by removing them one at a time. Neither asked whether the rule makes them right.

Which of the choices is doing the work measured how much each of those decisions is worth and found none of them carrying the stability alone. Partial pivoting is greedy. At each step it takes the largest available entry in the column and never revisits the choice, and greedy rules are not usually optimal. On a matrix small enough, the question can be settled rather than argued: there are n! orderings of the rows, every one of them defines an elimination, and each can be scored.

On a random matrix, greedy is often right and never far wrong #

Forty standard normal matrices at each size, with every ordering enumerated:

The share falls with the size, which it must — there are more orderings to miss — and the ratio does not grow with it. On the median 6×6 the greedy rule’s growth is 2.2 per cent above the best available, and its worst matrix of forty is 57 per cent above.

That is a good showing for a rule that looks at one column at a time and commits. It is also the case everybody’s intuition is built on, and it is not the case the bound is about.

It is worth being precise about what is being enumerated, because “every ordering” can mean two things. The search runs over row orderings and eliminates column k with whichever row the ordering names, whatever that row’s entry in column k happens to be. So it includes orderings partial pivoting would never take, orderings scaled pivoting would never take, and orderings that produce multipliers far above one — it is the whole of PA = LU over permutations P, not a search within some family of rules. The minimum it reports is therefore a genuine lower bound on what any row pivoting strategy can achieve, and the comparison is between a rule and the best that exists rather than between two rules.

What it does not include is column exchanges. Complete pivoting searches both, attains a growth bound that is polynomial rather than exponential, and costs an extra $n^3/3$ comparisons; the point of partial pivoting is that it does not do that. So every number here is about what row permutations alone can reach, which is the family the $2^{n-1}$ bound is a statement about.

The matrix built to defeat it #

Wilkinson’s matrix is the standard demonstration that the growth bound $2^{n-1}$ is attained: unit diagonal, −1 everywhere below it, a final column of ones, and nothing else. Partial pivoting applied to it makes no swaps at all — every entry in the active column has magnitude one, the rule takes the first of them, and the last column doubles at every step.

Enumerate the orderings and the minimum is not $2^{n-1}$.

It is 2, at every size, and the ordering that achieves it is one cyclic shift: eliminate with row 2 first, then rows 3, 4, … n, and row 1 last. Every multiplier in that elimination is exactly 1, which is the bound partial pivoting exists to enforce and enforces here too. So this is not a trade of one stability property for another. It is a legal elimination, by partial pivoting’s own standard, with a growth factor of 2 where the rule produces 64.

The matrix is not hard to eliminate. The rule is bad at it.

The tie that looks like the mechanism #

Every column of Wilkinson’s matrix, at every step, has all its candidate entries at the same magnitude. So the pivot search is not choosing the largest — it is breaking a tie, and how it breaks the tie is not part of any statement of the rule.

Two scans give two answers. A scan that keeps a strict improvement returns the first of the equal largest; a scan that keeps a non-strict one returns the last. Both are “take the largest”. Neither is more standard than the other, and neither is usually written down, because on a matrix whose entries come from anything continuous the set of equal largest entries has one member.

On Wilkinson’s matrix the difference is everything. Taking the last of the equal largest produces the cyclic shift, and with it a growth factor of 2 at n = 4, 6, 8, 10 and 12 — against 8, 32, 128, 512 and 2,048.

Which invites a one-line repair, and the repair does not work.

And the tie is not the mechanism #

Multiply the diagonal by 1 + 10⁻¹² and the ties are ties no longer: every column’s largest entry is now, strictly, the diagonal one. Both tie-breaks then agree, because there is nothing left to break, and both produce the greedy order and the exponential growth. At n = 7 the backward rule goes from 2 to 63.99999999974.

The good ordering has not moved. The exhaustive search on the perturbed matrix still finds 1.999999999999 at the same cyclic shift, with the same multipliers. It is exactly as available as it was, and no tie-breaking rule can reach it, because the greedy rule is now required to take the diagonal entry — which is larger by one part in a trillion.

So the sequence of facts is:

• there is an ordering with growth 2 and no multiplier above one;
• the greedy rule produces $2^{n-1}$;
• at exactly equal ties, one tie-break stumbles onto the good ordering;
• and a perturbation twelve orders of magnitude below the entries removes that accident without touching the good ordering at all.

The tie-break is a coincidence, not a repair. The mechanism is that the greedy rule must take the largest, the good first pivot is not the largest, and a margin of 10⁻¹² is enough to forbid it.

What the bound is a statement about #

None of this makes the $2^{n-1}$ bound wrong. It is a bound on what partial pivoting can do, it is attained, and the matrix that attains it is the one above. What the exhaustive search changes is what the attainment means.

The usual reading is that the bound is tight because some matrices really do grow: elimination has to produce large intermediate entries on them, and $2^{n-1}$ is how large. The measurement refuses that reading. The intermediate entries do not have to be large — there is an elimination of the same matrix whose largest intermediate is twice its largest entry — and what is tight is the rule’s inability to find it.

That is a different kind of tightness and it has a different consequence. A bound tight because of the problem is information about the problem and there is nothing to be done. A bound tight because of the rule is a statement about the rule, and it says there is something to look for.

The bound that is never attained measured the other side of the same statement — that random matrices come nowhere near $2^{n-1}$, so the bound is pessimistic in practice — and the two findings together locate it precisely. The bound is loose on almost every matrix, tight on one constructed family, and tight there because of a greedy decision rather than because of an obstruction.

It also says where to look. Which of the choices is doing the work found the early decisions carrying most of the value on a random matrix, and this is the same finding in its extreme form: on Wilkinson’s matrix every one of the n − 1 decisions is forced, and the one that matters is the first. Take row 2 at step 1 and the rest follows; take row 1 and nothing later recovers it, because the subsequent steps are all forced too and each doubles the last column.

That is what “a decision that cannot be unmade” means concretely. Elimination has no backtracking in it — there is no step at which the algorithm could notice that the last column has doubled four times and revisit step 1 — and the information that would have said so does not exist at step 1 in any form the rule reads.

What a non-greedy rule would have to do #

The good ordering is not findable by looking at one column. At step 1 the greedy rule sees a column of entries all of magnitude one (or, perturbed, one of them a trillionth larger) and has no information distinguishing them. The consequence of each choice is only visible n − 1 steps later, in the last column.

That is the structure of every combinatorial optimisation this field has met from the other side. The minimum-fill ordering is NP-hard and minimum degree is the greedy heuristic for it, and the order that decides the memory is the demonstration that the choice is worth a factor rather than a percentage; the same relationship holds here, with growth in place of fill. And the same measurement pattern applies: on random instances the greedy rule is optimal on a large share and never far off, and there exist constructions on which it is arbitrarily bad.

Whether minimising growth over row orderings is itself hard is not known to this field and is not settled here. What is settled is that the greedy rule does not solve it, that the gap on random matrices is a few per cent, and that the gap on the one matrix everybody cites is $2^{n-2}$.

What the last column is doing #

The mechanism is simple enough to state and is worth stating, because it explains why a shift of one row is all that is needed.

Eliminate Wilkinson’s matrix in its natural order. At step 1 the pivot is the 1 in position (1,1); every row below has −1 there, so every multiplier is −1, and subtracting −1 times row 1 from row i adds row 1 to row i. Row 1’s last entry is 1, so every last entry below gains 1: the column of ones becomes a column of twos. At step 2 the same thing happens to the rows below row 2, whose last entries are now 2, so they become 4. The doubling is the multipliers all being −1 in the same direction, and it compounds because each step’s pivot row already carries the previous step’s doubling.

Now eliminate with row 2 first. Row 2 has −1 in column 1, so it is a legal pivot and the multipliers formed against it are +1 for the rows below and −1 for row 1, which is left until last. The additions and subtractions no longer all point the same way: the last column picks up +1 from some steps and −1 from others, and the cancellation is exact. The largest intermediate entry over the whole elimination is 2 rather than $2^{n-1}$.

So what the greedy rule is missing is a sign, and the sign is not in the column it looks at. Both candidate pivots at step 1 have magnitude 1; what distinguishes them is what the multipliers formed against each will do to a column n − 1 places away.

What must fail for any of this to be wrong #

Three claims, each with a refusal attached. That greedy does not attain the minimum on every matrix — it attains it on 45 per cent of forty 6×6s, and a claim of 100 per cent fails. That it attains it on a real share of them — a claim that it is usually suboptimal fails. And that the good ordering on Wilkinson’s matrix survives the perturbation — a claim that the backward tie-break is a repair fails at ε = 10⁻¹².

The exhaustive search and the greedy rule are both scored by one routine that takes an explicit row order. That is the arrangement the earlier measurement explained and it matters more here: the claim is that two orderings of one matrix give different growth, and two implementations of elimination would make it a claim about two programs.

Why this is not an argument for complete pivoting #

The obvious response is that complete pivoting searches rows and columns, has a growth bound that is polynomial, and would not be caught by this. It would not, and it is still not the conclusion.

Complete pivoting costs $n^3/3$ extra comparisons — the same order as the elimination itself — which is why essentially no production code does it, and a pivot that searches one row and one column prices the intermediate option. The measurement here is about the rule almost everything actually uses, and what it says about that rule is narrower and more useful than “use a bigger search”: the exponential case is not an obstruction, it is a rule failing to see one step past its own column, and the repair that would fix it is a look-ahead rather than a wider search.

Those are different costs. A wider search compares more entries at every step; a look-ahead performs more eliminations at every step. On a dense matrix the second is dearer. On a sparse one, where the search is already restricted and the real currency is fill, neither is obviously the right shape — and a threshold between fill and growth is where that trade is priced.

One more thing is worth recording about the arithmetic, because it is the kind of detail that silently decides a measurement. The growth factor is the largest intermediate entry over the whole elimination divided by the largest entry of the original matrix, and “over the whole elimination” has to include the frames between steps rather than only the final U. On Wilkinson’s matrix the two agree, because the largest entry is in the last frame; on a matrix whose growth peaks in the middle they do not, and a routine that measured only U would report a growth factor that is too small by whatever the middle reached. The routine here takes the maximum after every step.

What this does not settle #

Sizes 4 to 7, because 8! orderings is the affordable ceiling and 12! is not. Nothing here says how the optimal share behaves as n grows, beyond that it is falling.

Forty matrices at each size, standard normal. The worst ratios quoted are the worst of forty.

The growth factor, not the backward error. An ordering with smaller growth permits a smaller backward error and does not guarantee one, and no ordering here is scored on the accuracy of a solve.

And the perturbation is applied to the diagonal only, at three magnitudes. A perturbation that broke the ties the other way — making a subdiagonal entry the largest — would hand the greedy rule the good ordering, which is the same coincidence with the opposite sign and is not measured.

Still open: whether the minimum is findable, and what a one-step look-ahead buys #

A look-ahead of one step. The greedy rule chooses the largest entry in the current column. A rule that chose the entry minimising the largest entry of the resulting trailing submatrix would cost n − k extra eliminations at step k — a factor of about n on the whole factorisation — and would see exactly the information the good ordering needs at step 1 of Wilkinson’s matrix. Whether it finds it, and what it is worth on the random matrices where greedy is already within two per cent, is one sweep and would price the next of these essays.

Whether minimum growth is hard. Minimum fill is NP-hard and the analogy is suggestive rather than an argument. The exhaustive search here is the tool that would settle small cases; a construction on which every non-optimal ordering is exponentially bad would be the evidence that the problem has the shape.

A family of adversaries rather than one. Wilkinson’s matrix is one construction. Whether every matrix on which greedy attains a growth near its bound has a low-growth ordering available, or whether some matrix genuinely requires exponential growth under every ordering, is the question this essay’s refusal is about and answers for exactly one matrix.

And what the good ordering costs elsewhere. The cyclic shift gives growth 2 on Wilkinson’s matrix. What it gives on a random matrix, and whether an ordering chosen for growth is a bad ordering for fill or for the sparsity a real code cares about, is the trade a threshold between fill and growth prices for a different pair of quantities and has not been priced for this one.