A doubling that arrives two steps late

One step ahead is one step short built the pivot rule the greedy rule’s critics always propose. At each column, try every candidate row as the pivot, perform the elimination, and keep the row whose elimination leaves the smallest largest entry in the trailing submatrix — the quantity the growth factor is a maximum of. On Wilkinson’s matrix that rule chose the greedy rule’s rows one for one and attained the same growth, $2^{n-1}$: every first pivot leaves the same largest entry, 2, and the doubling the greedy choice sets up only appears at the second elimination. A rule that scored each candidate over two eliminations saw it, took the other row, and held the growth at 2 on every size from 4 to 24.

The essay drew the general conclusion in a sentence and left it unproved: “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.” Its last section asked for “a block version of Wilkinson’s construction, perhaps, in which each doubling needs two eliminations to express.”

There is, and it is the simplest block version there could be.

Two copies, taking turns #

Take Wilkinson’s $m \times m$ matrix — ones on the diagonal, minus ones below it, ones down the last column — and replace every entry by that entry times the $2 \times 2$ identity. The result, $W_m \otimes I_2$, is a $2m \times 2m$ matrix; with the Kronecker product’s natural ordering of rows and columns it is two copies of Wilkinson’s matrix interleaved, the odd rows and columns holding one and the even the other.

No entry couples the two copies, so eliminating a column of one leaves the other untouched. Elimination works through the columns in order, and the columns alternate between the copies: step one belongs to the first copy, step two to the second, step three to the first again. A pivot decision in the first copy at step one meets its consequence at step three, when that copy is next eliminated — two eliminations later rather than one.

The ties are broken exactly as the earlier essays broke Wilkinson’s: the diagonal is scaled by $1 + 10^{-12}$, so that every rule meets the same tie-break and no difference below comes from it. The look-ahead rule is the earlier essay’s, generalised to any depth $d$: a candidate pivot is scored by the smallest worst largest-entry that any sequence of $d - 1$ further pivots can leave, and ties go to the lower row. At depths one and two it chooses the earlier essay’s rows exactly, on Wilkinson’s matrix and on this one.

The tie lasts as long as the deferral #

The first column of $W_4 \otimes I_2$ has four candidates, rows 1, 3, 5 and 7, all of magnitude one. Scored one step ahead, every one of them leaves a largest entry of 2: the elimination adds the pivot row into the others and the last column of the first copy becomes 2 wherever it was 1. Scored two steps ahead, still 2 for every candidate, because the second step is the other copy’s and does nothing to the first. A tie at both depths, broken towards row 1 — the greedy choice, which sets up the doubling.

Scored three steps ahead, the tie breaks. Row 1’s best continuation reaches 4 by the third elimination, when the first copy is eliminated again and the 2s it left are added to each other; rows 3, 5 and 7, which are Wilkinson’s good ordering for that copy, keep it at 2. So the three-step rule takes row 3.

That is the same picture the earlier essay drew for Wilkinson’s matrix one step earlier. There the tie lasted for one step of look-ahead and broke at the second; here it lasts for two and breaks at the third. The tie lasts exactly as long as the deferral, because what decides the choice is a single elimination that has not happened yet.

The doubling arrives d steps late #

With three copies the deferral is three. $W_5 \otimes I_3$ interleaves three Wilkinson matrices of size five, and each copy is eliminated at every third step. Along the order the three-step rule chooses, the largest active entry is 2 for the first three steps, 4 from the fourth, 8 from the seventh and 16 from the tenth: one doubling per round of the three copies, each arriving three steps after the decision that caused it. The rules looking one and two steps ahead choose the same order and trace the same staircase. The rule looking four steps ahead is standing on the step where each doubling lands, avoids every one, and keeps the largest entry at 2 throughout.

Every depth has its matrix #

This figure puts the three families on one axis.

On Wilkinson’s matrix — $W \otimes I_1$ — the rule looking one step ahead attains $2^{n-1}$ at every size measured, 8 at $n = 4$ and 2,048 at $n = 12$; looking two ahead, 2. On $W_m \otimes I_2$ the rules looking one and two steps ahead attain $2^{m-1}$, which is $2^{n/2 - 1}$: 4, 8, 16, 32 and 64 at $n$ = 6, 8, 10, 12 and 14, equal to the greedy rule’s growth to a millionth; looking three ahead, 2 at every size. On $W_m \otimes I_3$ the rules looking one, two and three ahead attain $2^{n/3 - 1}$ — 4, 8 and 16 at $n$ = 9, 12 and 15 — and looking four ahead gives 2.

So the answer to the earlier essay’s question is a construction rather than an argument. For every depth $d$, the matrix $W \otimes I_d$ defeats the look-ahead rule of depth $d$, and holds it to the greedy rule’s growth on that matrix, $2^{n/d - 1}$. Looking further ahead does not remove exponential growth from the worst case; it divides the exponent by the depth. A rule looking ten steps ahead, on $W \otimes I_{10}$ of size 100, would face growth $2^9 = 512$ — less than the $2^{99}$ partial pivoting faces on Wilkinson’s matrix of the same size, and still exponential in the size.

That is also a statement about the bound that is never attained. The classical bound on partial pivoting’s growth, $2^{n-1}$, is attained by Wilkinson’s construction and essentially never in practice. The look-ahead rules move the attained worst case down to $2^{n/d-1}$, and the constructions here attain that, so the bound for a depth-$d$ rule is at least that large. Whether it is larger — whether some other construction pushes a depth-$d$ rule above $2^{n/d - 1}$ — is open.

What the deeper rule finds #

The orders themselves say what the rules are doing. On every one of these matrices, every rule that looks no further ahead than the deferral takes the rows in their natural order, 1, 2, 3 and so on to $n$ — which is the greedy rule’s order, since every column’s candidates tie and every tie goes to the lowest row. The rule that looks one step further takes a cyclic shift by $d$ rows: on $W_4 \otimes I_2$, rows 3, 4, 5, 6, 7, 8, 1, 2; on $W_4 \otimes I_3$, rows 4 to 12 and then 1, 2, 3.

That shift is not a new ordering. It is the one the order the greedy rule cannot choose found by scoring every ordering of Wilkinson’s matrix — pivot on row 2, then 3, and row 1 last — applied to every copy at once. The rule that can see the doubling does not invent an escape; it finds the one the exhaustive search found, one copy at a time, without searching more than $d + 1$ steps. And the rule that cannot see it is not misled into some subtly bad order: it simply has nothing to prefer, and falls back on the order elimination takes when it is taught as a procedure with no decisions in it — the starting point elimination is a sequence of choices argued against.

The deferral is not a tie #

Everything above rests on a matrix whose first column is a tie, broken by $10^{-12}$. A worst case is as fragile as its margin found that Wilkinson’s growth under partial pivoting survives only as long as the perturbations stay under the margins its construction leaves, and it is fair to ask whether the deferral is a property of the tie rather than of the structure.

Perturb every nonzero entry by a random relative amount and the ties are gone. For Wilkinson’s matrix that is the end of the worst case: the essay on its margin found Gaussian noise of $10^{-14}$ taking its median growth under partial pivoting to exactly 2. the greedy rule now chooses by whichever candidate’s perturbation came out largest, and lands on growth 2, 4 or 8 — on 8, 9 and 3 of twenty draws — at every size of perturbation from $10^{-12}$ to a hundredth. The two-step rule does not do better. At perturbations of $10^{-12}$, where its own tie threshold still decides, it reaches the full 16 on 13 of twenty draws and is worse than the greedy rule on 17. From $10^{-9}$ to $10^{-3}$, where the noise decides its choices instead, it lands on 2, 4, 8 and 16 on 5, 8, 2 and 5 draws — the same median as the greedy rule, 4, worse than it on 7 draws and better on one — and at a hundredth the same, with one of the 16s at 15. The three-step rule’s growth is 2 on every draw at every size, to within 0.012 at the largest perturbation.

So the deferral survives the loss of its ties, in the sense that matters. Without a tie the two-step rule’s choice at the first column is decided by a perturbation it has no reason to read, exactly as the greedy rule’s is, and it is no better informed — two copies of Wilkinson’s matrix are as blind to it with noise as without. What noise cannot do is lend it a third step. The three-step rule is not deciding a tie; it sees a factor of two, and a perturbation of a hundredth does not move a factor of two.

What seeing further costs #

The look-ahead rule of depth $d$ scores each candidate by searching all continuations of length $d - 1$, and at each level of the search every remaining row is a candidate. So each further step multiplies the work by about the number of rows left.

Counted as trial eliminations over a whole factorisation of $W_4 \otimes I_3$, twelve by twelve, the rules looking one to four steps ahead perform 30, 109, 328 and 824; on $W_6 \otimes I_2$, also twelve by twelve, 42, 202 and 630. The factor per step of depth is between 2.5 and 4.8 at this size and grows with $n$, because these matrices are sparse and most columns have only a few candidates. On a dense matrix every unused row is a candidate and the factor is close to $n - k$ at step $k$: the depth-$d$ rule costs about $n^{d+3}$ operations against elimination’s $n^3$.

Put the two measurements together and the trade is stark. Each extra step of look-ahead costs a factor of about $n$ in work and buys a factor of $d/(d+1)$ in the exponent of the worst growth it can be held to. Going from depth two to depth three on a matrix of size 100 multiplies the work by about a hundred, and moves the worst case from $2^{49}$ to $2^{32}$. A pivot rule is not where exponential growth is cured.

What does cure it, and what that says about look-ahead #

The growth these constructions force is not unavoidable for the matrices themselves. On every one of them a rule looking $d + 1$ steps ahead finds growth 2; the order the greedy rule cannot choose found that a single cyclic shift of Wilkinson’s rows does the same with no look-ahead at all, and the same shift applied to each copy does it here. The matrices are easy. What is hard is a rule that finds the easy order from information it can see at the moment it has to choose.

That frames what look-ahead is. It is a search over orderings truncated at a fixed depth, and any truncated search can be fooled by a payoff placed one step past its horizon. The remedies that work in practice are not deeper searches but different information. Complete pivoting reads the whole active submatrix at every step and has a subexponential bound; a pivot that searches one row and one column measured rook pivoting, which reads a row and a column and kept the median growth of Gaussian matrices of size 64 at 2.53 against partial pivoting’s 4.06; and a threshold that holds the growth still measured what a threshold on the pivot — a bound on the multipliers — buys on the matrices whose growth is a margin. None of them looks forward in time. Each looks wider at the present step.

Which of the choices is doing the work found the same thing from the other end: on random matrices almost all of partial pivoting’s value is in the first few decisions, and the later ones barely matter. A construction like $W \otimes I_d$ is the opposite — a matrix whose every decision matters, and whose decisions matter late.

What three small families do not show #

The constructions are block-diagonal in disguise: no entry couples the copies, and the deferral comes entirely from the order in which elimination visits them. A matrix whose copies were coupled would let a decision in one leak into another sooner, and might be easier for the look-ahead rule, or harder. One coupling was tried — the copies sharing a last column — and gave the same growth, $2^{m-1}$, with depth two defeated and depth three escaping, but one coupling is not a survey. The sizes stop at fifteen because the depth-four rule’s search is already 2,068 trial eliminations there and grows like $n^5$. And the rules here look ahead with the same objective the earlier essay used, the largest active entry; a rule that looked ahead at the multipliers, or at a norm of the trailing matrix rather than its largest entry, is a different rule and might be defeated by a different construction or not at all.

Still open: a deferral that keeps the full rate, coupled copies, and a wider look #

A deferral that doubles every step. Interleaving $d$ copies holds the depth-$d$ rule to $2^{n/d-1}$, because each copy doubles only when it is visited. A construction that deferred each decision by two steps and still doubled at every step would hold the two-step rule to $2^{n-1}$. The prediction with a sign is that no such construction exists for the growth measured by the largest active entry — that any matrix on which the two-step rule attains growth $g$ at size $n$ has $\log_2 g \le n/2$ — and that an exhaustive search over the $\pm 1, 0$ matrices of size six finds none above $2^{3}$.

Copies that leak. Couple the copies by a small amount $\varepsilon$ between them — an entry of size $\varepsilon$ in every off-copy position of the first copy’s last column. The prediction is that for $\varepsilon$ above about $2^{-m}$ the leaked doubling reaches the two-step rule’s horizon and it escapes, so that the deferral needs its copies separated by more than the growth they are about to suffer.

Looking wider instead of further. Rook pivoting reads one row and one column at each step and needs no look-ahead. The prediction is that it attains growth 2 on every $W \otimes I_d$ at every size measured here, at a cost of at most three times partial pivoting’s comparisons — which would make the width of the present step, not the depth of the future, the dimension in which a pivot rule has to look.