Combinatorial search — where it appears
Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.
The order the greedy rule cannot choose
Wilkinson's matrix is the standard demonstration that partial pivoting's growth bound of 2^(n−1) is attained. It is attained by the row order the greedy rule picks, and not by the matrix: a single cyclic shift of the rows gives growth 2 at every size, with no multiplier above one. At n = 7 that is 64 against 2. And perturbing one entry by 10⁻¹² leaves the good order exactly where it was while putting every tie-break of the greedy rule back on 64.
One step ahead is one step short
Partial pivoting takes the largest entry in the column and, on Wilkinson's matrix, walks into growth of 2^(n−1) that a cyclic shift of the rows avoids entirely. A rule that chose instead the pivot whose elimination leaves the smallest trailing submatrix was expected to see the good order at the first step. It sees nothing there: every first pivot leaves a largest entry of exactly 2, and with the ties broken by 10⁻¹² it prefers the greedy row by 10⁻¹². It attains 2^(n−1) at every size. Looking two eliminations ahead, the greedy row scores 4 and every other row 2, and the growth is 2 at every size up to 24. On random matrices one step of look-ahead helps below n = 16 and is worse than greedy on more than half of them by n = 32.
An order found once knows what the rows know
Searching for a fraction-free elimination's least-cost row order costs forty to two hundred and sixty times the elimination, so it can only pay if one order serves a whole family. The prediction was that it cannot: the best order depends on which rows happen to have short entries, so a reused order should do no better than the natural one. On independent entries and on a shared zero pattern that holds — another member's best order is an ordinary order, at the middle of the 40,320. On a family that shares its row scales it fails completely: another member's order costs a median 1.13 of the least where the natural order costs 1.88. But on every family, including that one, the rule that just takes the smallest pivot entry is cheaper than any reused or trained order — 1.24, 1.08 and 1.01. What an order carries from one matrix to the next is what the family shares — and only when that is a particular matrix, not a visible structure, does an order trained on the family beat the rule.
A doubling that arrives two steps late
A pivot rule that looks one elimination ahead chooses Wilkinson's growth row for row, because the doubling it sets up arrives one step later; looking two ahead escapes it. The argument said a matrix whose damage arrives two steps late would defeat the two-step rule the same way. It exists, and it is two Wilkinson matrices interleaved: W ⊗ I₂. Every look-ahead of depth one or two reproduces the greedy rule's growth on it exactly, 4 to 64 from n = 6 to 14, and depth three gives 2. Three copies defeat depth three and yield to four. The growth each depth is held to is 2^(n/d − 1): a fixed depth stretches the exponential and never removes it, at a cost that rises by a factor of about n for every step it looks.
The doubling is in the row already
Interleave d copies of Wilkinson's matrix and every pivot rule that looks up to d eliminations ahead walks into growth 2^(n/d − 1); escaping costs a look one step deeper, and a deeper look multiplies its trial eliminations. Rook pivoting looks no further than the present step and escapes every one of them — growth exactly 2 at every deferral and every size — for 3.2 times partial pivoting's comparisons whatever the deferral. The doubling a look-ahead hunts for in the future is already visible in the row in front of it. And the leak that was supposed to let the two-step rule escape was placed where no pivot is ever chosen: at every size up to one, it changes nothing.
Named alongside it
The objects these essays reach for when they reach for this one.
Gaussian eliminationGrowth factorPartial pivotingLU factorisationPivotingExact ground truthKronecker productPermutationWilkinson's matrixArithmetic costBackward errorBit length