The doubling is in the row already

A doubling that arrives two steps late built a matrix to defeat a pivot rule that thinks ahead. Wilkinson’s matrix, with ones on the diagonal and in the last column and minus ones below, makes partial pivoting double the last column at every elimination, for growth $2^{n-1}$. One step ahead is one step short had found that a rule scoring each candidate by the largest entry its elimination leaves chooses that growth row for row, because the doubling it sets up arrives one step later, and that a rule looking two eliminations ahead escapes. The construction $W \otimes I_d$ — every entry of Wilkinson’s matrix replaced by that entry times the $d \times d$ identity, which interleaves $d$ copies — delays each copy’s consequence by $d$ eliminations, and it holds every rule looking up to $d$ ahead to the greedy growth $2^{n/d-1}$. Only depth $d+1$ escapes.

Its last section offered three ways forward, two with signed predictions. One was a leak: couple the copies by $\varepsilon$ in the first copy’s last column, and “for $\varepsilon$ above about $2^{-m}$ the leaked doubling reaches the two-step rule’s horizon and it escapes”. The other was to stop looking further and look wider. Rook pivoting, which a pivot that searches one row and one column priced on Gaussian matrices, reads the present column, then the largest entry’s row, then that entry’s column, until it holds an entry largest in both. “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.”

The leak does nothing at all, and the reason is worth having. The rook escapes everything, at a cost just over the stated bound, and the reason for that is the argument of this essay: the doubling a look-ahead hunts for in the future is already sitting in the row in front of it.

The rook escapes every deferral #

Sixteen matrices: Wilkinson’s of order four, six, eight and ten, interleaved once, twice, three times and four times, so from four rows to forty. Each is factored by partial pivoting, by rook pivoting and by complete pivoting, and each rule’s growth — the largest entry ever written over the largest entry of the matrix — is recorded with the number of entries its search compared.

Partial pivoting reaches $2^{m-1}$ on every one of them — 8, 32, 128 and 512 — as it must, since on $W \otimes I_d$ its choices are the greedy rule’s and each copy doubles once per visit. Rook pivoting reaches exactly 2 on all sixteen, and so does complete pivoting. Turn the dial: the picture is the same at every deferral, because it is the same matrix in each copy and the rook treats each copy the same way.

The look-ahead rules from the earlier essay needed depth $d+1$ to do this, which is depth five for four interleaved copies. The rook needs no depth. What it needs is to read the row.

What the rook reads that the look-ahead looks for #

Follow one step. At the first column of Wilkinson’s matrix every entry is $\pm 1$, the ties are broken a hair in favour of the diagonal, and partial pivoting takes the diagonal. The rook does too: the largest entry of the column is the diagonal one, the largest of its row is also one — the diagonal and the last column tie — and the tie keeps what it holds. One elimination later every remaining row has a two in its last column and a one or minus one elsewhere. Partial pivoting looks down the next column, finds ones, and takes the diagonal again; the two in the last column becomes a four.

The rook looks down the same column, takes the same entry, and then reads its row. The row holds the two. The rook moves to the last column, finds the two is the largest of that column as well, and pivots on it — a column interchange that brings the growing column forward and eliminates with it before it can double. From then on the growing entries are the pivots rather than the entries being updated, and nothing doubles twice.

That is the whole of the escape, and it explains why the deferral cannot touch it. The look-ahead rules score a candidate pivot by what eliminating it would do to entries several steps later. On $W \otimes I_d$ every candidate’s score is tied until the depth reaches the copy’s next visit, which is what the construction is for. But the entry those future steps would double is not hidden in the future: it exists now, in the last column, and every row the rule might pivot on contains it. A rule that reads one row of the active matrix sees the largest entry in it whatever the order of the copies. Interleaving changes when a copy’s doubling is used; it does not change where its growing entry is.

The order the greedy rule cannot choose found the same fact as an ordering: Wilkinson’s growth disappears under a cyclic shift of the rows, which puts the last column’s growth into the pivot at once. The look-ahead of depth $d+1$ finds that shift for every copy together. The rook finds it one step at a time, by looking sideways.

The price, and why it is three and a fifth #

The rook compares between 3.16 and 3.31 times as many entries as partial pivoting on every one of the sixteen matrices. Complete pivoting compares up to 27 times as many, at forty rows, and its ratio keeps growing with the size because it scans the whole active matrix at every step. None of the three counts depends on the deferral: four copies of order ten cost the rook what one copy of order forty would.

So the prediction’s growth clause holds and its cost clause misses by a few per cent, for a reason that is in the algorithm rather than in the matrices. A rook search reads a column, then a row, then a column, and stops only after two consecutive scans that find nothing larger. A step that never moves therefore costs three scans of the active length — the first column and two confirmations — and a step that moves once, as the rook does on most steps here to reach the last column, costs four. Three scans a step is the floor, not a ceiling, and on these matrices it averages a little over three because the scans shorten as the elimination proceeds while the moves cluster early.

The earlier essay on rook pivoting measured about the same ratio on Gaussian matrices — 6,987 entries against 2,080 at size 64 — and a walk of more than a hundred thousand on a matrix built to make the rook move at every scan. The deferred matrices are nothing like that: the rook moves once and stops. They are hard for rules that look ahead and easy for a rule that looks across.

Half a rook is enough here #

If the escape is the one move along the row, the confirmations are paying for nothing on these matrices. A half rook — the largest entry of the column, then the largest entry of that entry’s row, and stop, with no scan back down the new column — compares exactly two scans a step. Run on the same sixteen matrices it attains growth 2 on every one, at exactly twice partial pivoting’s comparisons, and the price figure above carries it as the fourth row of dots. It moves to the last column on every step but the first and last few, as the full rook does, and never needs to confirm that the entry it moved to is also the largest of its column, because on Wilkinson’s construction the growing column’s entry always is.

That is a statement about these matrices, not a recommendation. A pivot that is the largest of its row but not of its column produces multipliers larger than one in that column, and multipliers larger than one are what partial pivoting’s whole guarantee is built to forbid. On thirty Gaussian matrices of each size the half rook’s median growth is 1.51 at sixteen rows, 2.11 at thirty-two and 2.85 at sixty-four: between the full rook’s 1.42, 1.98 and 2.49 and partial pivoting’s 1.91, 2.91 and 4.03 at every size, with a worst draw of 4.4 at sixty-four against the rook’s 3.8 and partial pivoting’s 7.5. The confirmation scans buy about a sixth of the growth on random matrices and nothing on the deferred ones; partial pivoting’s extra growth over the half rook is the price of never reading a row at all.

So the distance between partial pivoting and the escape is one row scan per step, and on matrices whose damage collects in one column, that scan finds it. Where the multipliers go follows the other half of the trade, the size of the multipliers a pivot rule allows, and it is the half the rook’s confirmation scans exist to protect.

What the deeper look pays #

The look-ahead that escapes is not free either, and it is priced in a different unit.

On the seven matrices small enough to run it, the look-ahead of depth $d+1$ performs between 26 and 354 trial eliminations, against the rook’s 33 to 180 comparisons. The counts look comparable and are not: a trial elimination updates every entry of the active matrix, so each one costs as much as a whole column of comparisons squared. At eight rows, the three-step rule needed for two copies performs 173 trial eliminations where the two-step rule needed for one copy performed 132, and each further step of depth multiplies the tree of candidates it explores. The rook compares 115 to 119 entries on both.

The earlier essay found the depth-$(d+1)$ rule escaping by choosing the cyclic shift for every copy at once: an ordering decision made with a view of the whole future. The rook makes no ordering decision. It takes a column interchange each time the row it is in holds something larger than the column does, and that local rule reproduces the effect of the global one on every matrix here.

The leak that was never consulted #

The second prediction was that coupling the copies would let the two-step rule escape: an entry $\varepsilon$ in every off-copy position of the first copy’s last column, so that the copies could see each other’s doubling early.

At every $\varepsilon$ from $2^{-30}$ to one, on the copies of order five and six, the named leak leaves both the greedy rule and the two-step rule at exactly $2^{m-1}$ — 16 and 32. Not approximately: to a millionth. The leak sits in the first copy’s last column, and the last column is the one column of $W$ that no pivot rule ever chooses a pivot from until the final step, because the greedy order eliminates the columns in sequence and the look-ahead’s scores depend only on the entries a candidate’s elimination writes. An entry in that column is carried along with every row operation and consulted by no decision. Coupling there is coupling in name only.

A leak where decisions are made behaves differently. With $\varepsilon$ times a Gaussian in every off-copy position, ten draws at each size, the greedy rule’s median drops from 16 to 12 at $2^{-20}$ and to 4 from $2^{-16}$ on — the random entries break Wilkinson’s ties, which were held by a margin of $10^{-12}$ — and the two-step rule’s median drops to 3. But its worst draw stays at 16 up to $2^{-6}$, and on the copies of order six at 16, half of the undisturbed 32. A leak that reaches the decisions does not hand the two-step rule the information it lacks; it changes which ties exist, and on some draws the new ties defer the doubling as well as the old ones did. The rook’s worst draw stays at 2 up to $2^{-4}$ and reaches 2.4 only when the leak is a quarter of the entries it couples.

A worst case is as fragile as its margin found Wilkinson’s growth collapsing under noise of $10^{-14}$ for exactly this reason: the matrix is extreme only because its ties are exact. The interleaved matrices inherit that fragility for the greedy rule and lose it for the look-ahead, which keeps finding new deferrals in the perturbed ties. The rook needs no tie to be broken, because the entry it reacts to is the largest in its row by a factor of two.

The perturbations that kept the look-ahead blind #

The earlier essay’s own test makes the same point from the other side. Perturbing every nonzero entry by a relative $10^{-12}$ to $10^{-2}$, twenty draws at each size, it found the two-step rule still reaching 16 — worse than the greedy rule’s worst, 8 — while the three-step rule stayed at 2. On the same draws the rook stays at 2, to within a part in a hundred at the largest perturbation. The three-step rule and the rook escape together, and only one of them had to search a tree to do it.

What sixteen matrices do not show #

Every matrix here is built from Wilkinson’s, so every one has its growing entries in a single column that the row scan finds at once. A construction whose damage is spread across many columns, each small at the step it could be seen and large only after it combines with others, would not be read off one row; whether such a construction exists for the rook is the question the rook’s own literature answers with a bound on its growth that is far below partial pivoting’s and far above two, and these measurements do not test it. The bound that is never attained is the corresponding story for partial pivoting. The cost comparison with the look-ahead counts trial eliminations and does not weigh each by the size of the active matrix it updates; the measured counts are given and the weighting is argued, not measured. And which of the choices is doing the work suggests the rook’s single column interchange per step is doing nearly all of it here, which is asserted by the explanation above and not separated by an experiment that forbids it.

Still open: damage spread over columns, and a matrix that punishes half a rook #

A construction for the rook. A rook search sees the largest entry of the row it lands in. A matrix whose growth is carried in two columns at once, each only half the size of the diagonal at the step it could be read and doubling only once the two are combined, would hide its damage from one row scan. The prediction with a sign is that interleaving two such columns in Wilkinson’s construction gives a matrix on which the rook’s growth exceeds $2^{n/4}$ at order sixteen and above, while complete pivoting’s stays under four — so that the rook can be defeated by spreading the damage, as the look-ahead was by delaying it.

A matrix built for the half rook. The half rook trusts the row and never checks the column it moves into, so its pivot can be far from the largest in that column. The prediction with a sign is that Wilkinson’s matrix with its last column scaled by one half — so that the row scan’s move lands on an entry each column holds a larger one than — gives the half rook growth above $2^{n/2}$ at order sixteen and above, while the full rook stays under four: the confirmation scans the deferred matrices did not need are what such a matrix would make the rook pay for.