One step ahead is one step short

The order the greedy rule cannot choose scored every row ordering of Wilkinson’s matrix and found that the growth factor of $2^{n-1}$ partial pivoting attains on it is not the matrix’s. A single cyclic shift of the rows — pivot on row 2, then 3, and so on, and on row 1 last — gives growth 2 at every size, with no multiplier above one. The greedy rule takes the largest entry in each column; every entry in Wilkinson’s first column has magnitude one; the rule takes the first of the tied rows, and that choice doubles the last column at every subsequent step. Break the ties by $10^{-12}$ in the diagonal’s favour and every tie-break the greedy rule could use takes the doubling path.

That essay ended by proposing the obvious repair. The greedy rule reads one number per candidate row, the size of its entry in the pivot column. A rule that performed the elimination step with each candidate and kept the one leaving the smallest largest entry in the trailing submatrix would read the quantity the growth factor is actually a maximum of. It would cost $n - k$ trial eliminations at step $k$ — about $3n/4$ times the whole factorisation’s work — and, the essay said, it “would see exactly the information the good ordering needs at step 1 of Wilkinson’s matrix”.

It would not. What it sees at step 1 is a tie.

The rule, and a second one #

Two rules are measured. The one-step rule, at each column, tries every row with a nonzero entry as the pivot, measures the largest entry of the active submatrix that elimination leaves, and keeps the row with the smallest. The two-step rule scores each candidate by the best it can do over two eliminations: for each first pivot it tries every second pivot, and scores the first by the smaller of the pair’s worse largest entry. Both break exact ties in favour of the lower row index, as the greedy rule does, so that none of the differences below comes from a tie-break.

The one-step rule costs about $\sum_k (n-k)^3 \approx n^4/4$ operations against elimination’s $n^3/3$. The two-step rule costs a factor of $n$ more again, about $n^5/5$. Neither is a practical pivot rule on a large dense matrix, and neither is proposed as one. The question is whether looking ahead finds what the greedy rule misses, and how far ahead it has to look.

Wilkinson’s matrix, one step ahead #

The one-step rule attains $2^{n-1}$ at every size: 8, 32, 128, 2,048, 32,768 and 8,388,608 at n = 4, 6, 8, 12, 16 and 24, exactly the greedy rule’s numbers. It does not merely fail to find the good ordering. It chooses the greedy ordering, row for row.

The first step shows why. Pivot on row 1, the greedy rule’s choice: every other row has −1 in the first column and 1 in the last, and adding row 1 to it makes the last entry 2. Pivot on row 2 instead, the good ordering’s choice: row 1 subtracts a multiple of row 2 and its last entry becomes 2 as well; the rows below subtract row 2, which empties their last column and makes their second-column entries −2. Every choice of first pivot leaves the same largest entry. The 10⁻¹² perturbation that breaks the column ties breaks this tie too, by the same amount: the greedy row leaves exactly 2 and every other row leaves 2 plus a unit or two in the twelfth decimal. So the one-step rule, reading honestly, prefers the greedy row by $10^{-12}$ — and the damage it cannot see is a factor of two that arrives at the next step.

The damage arrives a step late #

Traced step by step at n = 16, the two orders leave the same largest entry after the first elimination, 2. After the second they have parted: the greedy order’s is 4 and the good order’s 2. From there the greedy order doubles every step, to 32,768 after the fifteenth, and the good order stays at 2 throughout. The first step is where the decision is made and the second is where its consequence becomes visible, and a rule that looks one step ahead is standing on the first.

The two-step rule is standing on the second. Scored over two eliminations, row 1 is 4 — its best continuation cannot avoid the doubling it set up — and every other row is 2. It takes row 2. At every later step the same reading picks the good continuation, and the growth is 2.000 at every size from 4 to 24. That is the growth the exhaustive search found possible at n = 7, reached by a rule that never looks more than two eliminations into the future.

There is a general statement hiding in the particular one. Wilkinson’s construction is built so that a pivot decision’s cost is deferred: the first elimination copies the last column into every row without changing its size, and the doubling needs a second elimination to happen. A look-ahead of depth $d$ sees consequences that arrive within $d$ steps, and any construction whose decisions pay off later than that defeats it in the same way. Whether there is a Wilkinson-like matrix built to defer by two steps — and so defeat the two-step rule as completely as this one defeats the one-step rule — is not answered here, and the argument suggests there is.

Forty small matrices, searched exhaustively #

Wilkinson’s matrix is one construction, chosen to defeat the greedy rule. The more ordinary question is what looking ahead does on matrices nobody built. At n = 6 and 8 every row ordering can be scored — 720 and 40,320 of them — so each rule’s growth can be compared with the least growth any ordering allows.

At n = 6 the greedy rule attains the exhaustive minimum on 18 of 40 matrices, the one-step rule on 26 and the two-step rule on 33. At n = 8 the counts are 10, 17 and 22. Each step of look-ahead finds the minimum on five to eight more matrices of forty. The medians move less: at n = 8 the greedy rule’s median growth is 1.075 times the best ordering’s median, the one-step rule’s 1.037 and the two-step rule’s 1.024. On a random matrix the greedy rule is rarely far from optimal, which which of the choices is doing the work had already found from the other side — removing a single decision barely moves the median — and looking ahead mostly converts near-misses into hits.

But not always. The one-step rule grows more than greedy on 7 of the 40 matrices at n = 6 and 10 at n = 8, and its worst at n = 8 is 2.96 against greedy’s 2.18. A rule that picks the smallest next submatrix will sometimes pick a pivot far smaller than the column’s largest — its largest multiplier on these matrices reaches 5.1 — and a large multiplier is a cost that the next submatrix does not show and a later one does. It is the same deferral as Wilkinson’s, arriving from the rule’s own choices.

As the matrices grow #

On a hundred random matrices at each size to n = 32 the one-step rule’s advantage shrinks and then reverses. Its median growth is 1.628 against greedy’s 1.704 at n = 12, 1.754 against 1.865 at 16, 2.241 against 2.356 at 24 — four to six per cent better — and 2.719 against 2.670 at n = 32, two per cent worse. The two-step rule holds its advantage longer: 1.499, 1.674, 2.025 and 2.563 at the same sizes, twelve, ten, fourteen and four per cent below greedy. In the tail it does more: at n = 32 its ninetieth percentile is 3.110 where greedy’s is 3.759.

Counted matrix by matrix, the fade is plainer. The one-step rule is worse than greedy on 18 per cent of matrices at n = 6, 33 per cent at 16 and 56 per cent at 32. The two-step rule is worse on 8 per cent at n = 6 and settles near 30 per cent from n = 16 on. A rule that looks a fixed distance ahead sees a fixed fraction of a factorisation whose length is n, and the fraction shrinks as n grows. At n = 6 one step is a fifth of the future; at n = 32 it is a thirty-first, and what the rule cannot see starts to outweigh what it can.

What each rule pays to look #

The costs are worth writing out, because they are what any look-ahead has to be weighed against. Elimination itself does about $\sum_k (n-k)^2 \approx n^3/3$ multiply–adds. The one-step rule does a trial elimination for each of the $n - k$ candidates at step $k$, each costing $(n-k)^2$, so about $\sum_k (n-k)^3 \approx n^4/4$: at n = 32 that is 24 times the factorisation. The two-step rule does a trial elimination for each pair of first and second pivots, about $n^5/5$ in all, which at n = 32 is 600 times the factorisation. Partial pivoting’s search, by comparison, is $n^2/2$ comparisons, a vanishing fraction of the arithmetic, and complete pivoting’s is $n^3/3$ comparisons, the same order as the arithmetic.

So the one-step rule is priced like complete pivoting multiplied by the matrix size, and the two-step rule like complete pivoting multiplied by its square. Neither bought, on random matrices at n = 32, what complete pivoting buys: a median growth well under two. What the look-ahead rules are designed to buy, and nothing else in this list is, is an ordering read from the matrix’s future rather than from its present — on Wilkinson’s matrix, the ordering the exhaustive search found, reached by the two-step rule and by no rule that reads only the current column. Elimination is a sequence of choices put the whole subject in one sentence: there is one decision at every step, and every stability property comes from making it well. The look-ahead rules make it with more information, and the measurements say how much the extra information is worth.

Exact ties, and why the perturbation matters #

Everything above uses Wilkinson’s matrix with its ties broken by $10^{-12}$, because the unperturbed matrix is a test of tie-breaking rather than of pivoting. With the ties left exact, every candidate at the first step scores exactly 2 one step ahead, and the one-step rule’s choice is whatever its tie-break says — the lowest row index here, which is the greedy row. A rule breaking its ties towards the highest index would take row 8 and, as the essay on the greedy rule found for the backward tie-break, might land on a good ordering by accident. That is not a property of looking ahead. It is the fragility the order the greedy rule cannot choose measured: a result that depends on which of several equal numbers a scan meets first is a result about the scan, and a perturbation of $10^{-12}$ is the smallest honest way to take the scan out of it.

The direction of the perturbation is chosen, and that choice matters too. It favours the diagonal, which keeps the greedy rule on its worst path; it is the adversary’s perturbation. A worst case is as fragile as its margin added random noise instead, of $10^{-14}$ to every entry, and found partial pivoting’s median growth on Wilkinson’s matrix falling to exactly 2, because random noise breaks the ties in random directions and most of them are not the doubling one. Under random noise the one-step rule would presumably share the same luck; that is not measured here. Under the adversary’s perturbation it inherits nothing, which is the test a pivot rule has to pass if it is to be credited with seeing the construction rather than with being shaken off it. A threshold that holds the growth still drew the same line from the other side: under partial pivoting Wilkinson’s growth rests on exact ties, while a threshold rule holds the same growth by row counts that no perturbation of the values reverses — the difference between a result about the matrix and a result about the scan.

The perturbation matters for the two-step rule as well, in the other direction. Its preference for row 2 over row 1 is a factor of two, 4 against 2, not a difference in the twelfth decimal, so no perturbation of that size can move it. The two-step rule’s success on Wilkinson’s matrix is robust in exactly the way the one-step rule’s failure is not accidental: both follow from where the doubling happens, one step after the decision that causes it.

What the search was worth #

The measurements put a price on the idea. The one-step rule costs about $3n/4$ times the factorisation, and buys nothing on the matrix it was proposed for and a few per cent on small random ones, reversing by n = 32. The two-step rule costs $n$ times more again and buys the Wilkinson ordering outright and ten to fifteen per cent of median growth at moderate sizes. Neither is a pivot rule anyone would ship for dense factorisation, where a pivot that searches one row and one column keeps the median growth at 2.53 on Gaussian matrices of size 64, against partial pivoting’s 4.06, for a search about three times the column’s — better at twice the size than the two-step rule manages at n = 32, for a small fraction of its cost. Rook pivoting reads a different quantity from either look-ahead: not the future’s size, but whether the chosen entry is also the largest in its own row, which is a statement about the multipliers the next steps will use.

What the measurements say is where the greedy rule’s failures live. They are not in the step’s own numbers, which the greedy rule reads correctly — the largest entry is the safest single pivot. They are in the interaction between successive steps, where a choice that is harmless now sets up a doubling later. The bound that is never attained found that on random matrices the doubling almost never compounds; Wilkinson’s matrix is built so that it always does, and it takes a rule that reads two steps of interaction to see the construction at all.

What this does not settle #

Standard Gaussian matrices and one adversarial construction. Matrices with structure — banded, or arising from a boundary-value problem, which the growth a boundary-value problem supplies found supplying large growth under partial pivoting naturally — may reward look-ahead more or less, and are not measured.

Look-ahead of depth two is the deepest measured, because depth $d$ costs $n^{d+3}$ and n = 32 at depth two already takes seconds a matrix. Whether depth three buys at n = 32 what depth two bought at n = 16 — whether the useful depth scales with n — is the obvious question and is not asked.

Still open: an adversary for two steps, and a look-ahead that reads the multiplier #

A construction that defers by two. The argument above says Wilkinson’s matrix defeats the one-step rule because its damage arrives one elimination late. A matrix whose damage arrives two eliminations late would defeat the two-step rule the same way. Building one — a block version of Wilkinson’s construction, perhaps, in which each doubling needs two eliminations to express — and confirming that the two-step rule attains its bound there while the three-step rule does not would turn the argument into a theorem about what look-ahead of fixed depth can guarantee: nothing, against an adversary allowed to defer.

A one-step rule with a multiplier bound. At n = 32, three in four of the matrices on which the one-step rule loses to greedy used a multiplier above two somewhere, against one in two of those on which it did not. A rule that looks one step ahead only among candidates within a factor of the largest — so that no multiplier exceeds, say, two — was tried alongside and behaves like the unbounded rule on the median, but whether its tail is lighter at n = 32 and beyond, where the unbounded rule’s multipliers reach 6.3, is the measurement that would say whether the reversal is the look-ahead’s or the multipliers’.