Elimination order — where it appears
Named by 9 essays across 6 fields — each of them below, with the objects they name alongside it.
Two ends of the same arrow
One matrix, one row moved from the front of the elimination order to the back, and the factor goes from completely dense to no fill at all. Both factorisations are exact to rounding, and nothing numerical chose between them.
The same matrix, numbered twice
One symmetric permutation. The condition number is 24.3948 either way to eight digits and the Frobenius norm is 6.13996414·10³ either way to twelve. The partition that stored 27,008 numbers now finds no admissible pair anywhere and stores all 65,536, and the format that compresses regardless stores 118,208.
The order the products are taken in
The sparsity field's first essay says the elimination order decides the memory. This is the same sentence about arithmetic: a contraction of several tensors over shared indices has one value and many evaluation orders, and on the inner product of two trains they differ by a factor of two million.
The fill that is not independent
Eliminate both halves of a grid and what is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged. Its off-diagonal block is 11 by 12 and six columns describe it to eight digits. Renumber the separator and the same block needs all eleven.
The order a batch arrives in
Sixteen problems over a parameter, solved in the order the loop produced them, cost a median of 1.54 times what the same sixteen cost sorted, and 2.80 times at the worst shuffling. A nearest-neighbour path computed from the parameter values alone recovers the sorted cost exactly, at every drift and every shuffle.
The plan that was right at rank four
An evaluation order is chosen once and paid for thousands of times, and the dimensions it was chosen at are not the dimensions it runs at. Compiled at rank four and run at rank 256 it costs 8.01 times the order that rank deserves; compiled at 256 and run at 2 it costs 301 times. A one-line rule recomputed on arrival costs 2.92 and 1.11.
The scale that only moved a pivot
Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.
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.
The switch is read before the solve
Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.
Named alongside it
The objects these essays reach for when they reach for this one.
Fill-reducing orderingFlop countRow scalingArithmetic costCondition numberContraction orderEquality-constrained least-squaresFill-inHeuristicHierarchical matrixLagrange multiplierOff-diagonal rank