What reading the next pivot buys

The pivot is in every product priced a fraction-free elimination by its arithmetic rather than by the size of its numbers. Bareiss’s algorithm keeps every intermediate an integer — each is a minor of the original matrix, and every update is divided exactly by the previous pivot — and the cost of doing it, counted as the sum over every multiplication and division of the product of its operands’ bit lengths, depends on the order the rows are taken in far more than the bit-length profile does. On twelve 8 × 8 matrices, where all 40,320 row orders can be run, the natural order cost 1.748 times the least and the rule that picks the smallest nonzero pivot entry 1.165. The reason was the pivot’s double duty: it multiplies every entry of its own step, and it divides every entry of the next.

That made a rule that reads two pivots the obvious next step. “The division by the previous pivot is the largest part of the cost, so each pivot is paid for twice: once as a multiplier at its own step and once as a divisor at the next. A rule that chose the pivot to keep the product of this pivot’s length and the next one’s small … might close more of the distance to the least-cost order than the smallest pivot’s 1.165. The exhaustive search at n = 8 is the instrument that would say.”

The earlier figure is the starting line. The rules that read rows — the shortest original row, the shortest current row — sat at 1.4 to 1.6 times the least cost, the smallest pivot at 1.165, and the area under the bit-length profile barely separated any of them. Whatever room is left is in the cost, and it is the smallest pivot’s remaining sixth that a look-ahead has to find.

Four rules that look ahead #

The rules are run on twenty-four matrices — the earlier essay’s twelve and twelve more from the same family, 8 × 8 with entries uniform in $\pm 6$ — and every one is placed against the least cost any of the 40,320 row orders reaches on the same matrix. Beside the natural order and the smallest pivot, four rules read further:

• The cheapest step simulates the elimination step each candidate pivot would perform and takes the one whose step costs least. It reads the pivot’s first duty exactly and its second not at all.
• Two pivots ahead simulates each candidate’s step and then each possible next pivot’s step, and takes the candidate whose step plus cheapest next step is least. It reads both of a pivot’s duties.
• Three pivots ahead does the same over three steps.
• Smallest, then next takes the shortest pivot entry and breaks ties in bit length by the smallest pivot the step leaves for the step after — the cheap form of reading two pivots, with no step simulated.

A seventh, which estimates the two steps from bit lengths instead of computing them, is measured in its own section below.

The question for each is how close it comes to the least, on the median matrix and on the worst, and how often it finds the least exactly. The figure below is every rule at once.

The cost being minimised is worth keeping in view, because exact arithmetic is the one setting in this field where the rounding error is zero and the cost is not. An answer with no error in it solved an integer system over the rationals and found the price had moved from accuracy to length: nothing is rounded, and every operation is paid for in the size of its operands. The answer is longer than the question showed that the output of an exact solve is unavoidably long. What a pivot order controls is the length of everything in between, and the schoolbook count — every multiplication charged at the product of its operands’ bit lengths — is that length turned into work. On these matrices the entries start at three or four bits and the intermediates reach twenty-odd; a product of two twenty-bit integers costs twenty-five times one of two four-bit integers, so an order that keeps intermediates a few bits shorter at the steps where most products happen saves a real share of the bill.

Reading one step’s cost reads no more than the pivot did #

The cheapest-step rule has a median of 1.187 times the least, against the smallest pivot’s 1.199, and its worst is 1.574 against 1.609. On the twenty-four matrices that is no improvement worth the name, and it finds the least exactly on one of them where the smallest pivot finds it on none. The cheap tie-break does no better: smallest-then-next has a median of 1.217 and a worst of 1.891, the worst of every rule.

The tie-break rule’s failure is worth a sentence of its own, because it is the cheapest way anyone would think of to read two pivots. It groups the candidates by the bit length of their pivot entry and, within the shortest group, takes the one whose step leaves the smallest next pivot. On most matrices the shortest group has one or two members and the rule is the smallest pivot under another name — its median, 1.217, is within two hundredths of it. But a group defined by bit length is coarser than the smallest entry: a pivot of 4 and a pivot of 7 have the same length, and choosing between them by what they leave behind gave up the one thing the smallest pivot reads exactly. On matrix 943 it costs 1.891 times the least, slightly worse than the two-step rule, for the same reason.

That is the earlier essay’s mechanism confirmed from the other side. The smallest pivot entry was already the best single-step proxy for a step’s cost, because the pivot multiplies every entry of the step and the other operands are fixed by the matrix; simulating the step adds the cross terms and the division, and they move the choice on few matrices. What the smallest pivot cannot see is the second duty, the division its successor’s step will carry, and a rule that reads only one step cannot see it either.

Two pivots ahead, and the matrix it loses on #

Reading the next step changes the picture. The two-pivot rule’s median is 1.025 times the least: three quarters of the distance the smallest pivot left is gone, and on eight of the twenty-four matrices the rule finds the least exactly. On the matrices where the smallest pivot did worst — 1.609, 1.354, 1.313 — it reaches 1.000, 1.002 and 1.000. That is the prediction the earlier essay made, and on the median matrix it is right by more than it asked for.

The dial’s second stop shows the exception. On one matrix, number 943, the two-pivot rule costs 1.871 times the least, where the smallest pivot costs 1.165 — worse than the smallest pivot is on any of the twenty-four, and second only to the natural order’s worst of 2.406. It is cheaper than the smallest pivot on nineteen matrices, the same on three, and dearer on two, and one of the two is that.

The step-by-step costs say what happened. The two-pivot rule’s first steps are as cheap as the least-cost order’s or cheaper — it found a pair of pivots that made steps one and two inexpensive — and its later steps are expensive, three to four times the least-cost order’s at steps four to six. A rule that charges two steps chooses the cheapest pair it can see, and a cheap pair can leave the remaining rows with long entries and no short pivot among them; the bill arrives at steps the rule never charged. The dial’s third stop, the estimated version of the same rule, makes the same choice on this matrix and is described below. It is the horizon effect of any greedy search with a fixed depth, and one step ahead is one step short met the same thing in floating-point elimination, where a rule that looked one step ahead at growth was defeated by a matrix whose damage arrived one step later.

Three pivots ahead #

Charging three steps finds the least of all 40,320 orders on thirteen of the twenty-four matrices, has a median of exactly 1.000, and its worst is 1.267 — on matrix 943, where the two-pivot rule’s 1.871 came from; the third step sees the bill the second did not. It is the best rule measured on every summary: median, worst and count of exact hits. Of the matrices where it does not find the least, it is within five per cent on eight.

So the distance between a local pivot rule and the least arithmetic is mostly a matter of horizon. A rule that reads one pivot leaves a fifth of the cost on the table; reading two takes most of it back and introduces a tail; reading three takes nearly all of it back and shortens the tail. Nothing about the measurement suggests that a fourth step would find much: the three-step rule is already at the least on more than half the matrices, and on the rest it is within a few per cent but for two.

And none of it pays #

Every look-ahead rule chooses by doing the work it is trying to avoid. The cheapest-step rule simulates one step per candidate at every step — eight candidates, then seven, down to two — and its simulations cost 5.9 times the least elimination on the median matrix. The two-pivot rule simulates every candidate and every successor, 42.8 times. The three-pivot rule simulates every candidate, successor and third pivot, 260 times. The elimination each one produces saves at most a fifth of one elimination over the smallest pivot. No look-ahead measured here comes within a factor of five of paying for itself, and the one that saves the most costs the most.

That is the real answer to the earlier essay’s question. Reading two pivots closes most of the distance to the least-cost order, and the distance was worth closing — the smallest pivot’s median matrix pays a fifth more than it has to. But a rule that reads the next pivot by computing the next step has spent the step to learn its price. The smallest pivot is cheap because it reads one number per row; any rule that improves on it has to read the next step’s cost from something cheaper than the step.

A reading that estimates instead of simulating #

The obvious way out is to estimate the next step’s cost instead of performing it. A step’s cost is a sum of products of bit lengths, and the bit length of each new entry $(p\,a - b\,c)/q$ is, to within a bit, the larger of $\operatorname{len}(p) + \operatorname{len}(a)$ and $\operatorname{len}(b) + \operatorname{len}(c)$, less $\operatorname{len}(q)$ — the division is exact, so it removes the divisor’s length. Every quantity a look-ahead needs can therefore be carried on a matrix of lengths, small integers, without forming a single large product. Choosing that way costs no bit-products at all; the real elimination is then run in the order chosen.

The estimate keeps little. On the same twenty-four matrices the estimated two-step rule has a median of 1.160 times the least, against the simulated rule’s 1.025 and the smallest pivot’s 1.199; it finds the least on two matrices, where the simulated rule found it on eight; and it is cheaper than the smallest pivot on thirteen matrices and dearer on seven. A bit of error in each estimated length, compounded over the sixty-odd entries of a step and over two steps, is enough to reorder candidates whose true costs differ by a few per cent, and those are exactly the candidates a look-ahead exists to tell apart.

And on matrix 943 the estimated rule costs 1.871 times the least — the same choice, to three figures, that the simulated two-step rule made. Its tail is not an artefact of simulation; it is the horizon. Both rules see two steps, both find the same cheap pair, and both pay for it at steps four to six. A better estimate could recover the median the simulated rule reached, but no estimate of two steps can see the third.

So the arithmetic has a shape that no cheap rule measured here escapes. The smallest pivot is cheap and leaves a fifth of the cost. A two-step look-ahead recovers most of that fifth only when it computes the steps it reads, which costs forty times the elimination, and keeps a tail either way. A three-step look-ahead removes the tail and costs two hundred and sixty times. Three orders and one last entry found that no order can move the elimination’s peak — the last entry is the determinant — and these measurements add the companion fact about its cost: the order can move it by a fifth, and finding the order that does is far more expensive than the fifth.

That is not a reason to stop at the smallest pivot in every setting. An elimination that is run many times on matrices of one structure — the same sparsity, entries from the same distribution — could pay for a search once and reuse the order it finds, and on twenty-four random matrices the three-step order and the least-cost order were the same thirteen times. Whether an order found on one matrix of a family is near the least on its siblings is the measurement that would say whether the search can be amortised; every intermediate is a minor suggests why it might, since the minors a row order produces depend on the matrix only through which rows meet first.

The least fill there is found the same pattern in sparse elimination, where every order was searched and the cheap local rule placed against the optimum: a greedy rule near the optimum on the median and occasionally far from it, for reasons no single step can see.

What twenty-four matrices do not show #

One size, eight, because the least-cost order has to be found by trying all 40,320; at larger sizes the look-ahead rules can still be compared with each other and with the smallest pivot but not with the least. One family, uniform entries in $\pm 6$, where rows do not differ much in length; the pivot is in every product found that spreading the rows’ lengths separates rules that read rows from rules that read pivots, and a look-ahead might separate further there. And one cost model, schoolbook multiplication, which is right for integers of tens of bits and wrong for integers of thousands, where a subquadratic multiplication makes a long operand relatively cheaper and the pivot’s double duty a smaller share of the bill.

Still open: an order found once, and what the least-cost order looks like #

An order reused across a family. The three-step order matched the least-cost order on thirteen of twenty-four matrices, at two hundred and sixty times an elimination’s cost to find. If the order found on one matrix is within a few per cent of the least on matrices drawn from the same family — the same size, the same entry distribution, or the same sparsity — the search is paid once and amortised. The prediction with a sign is that it is not: on these matrices the least-cost order depends on which rows happen to have short entries in which columns, and a reused order should do no better than the natural order’s 1.733.

What the least-cost order looks like. On thirteen matrices the three-step rule reproduces the least-cost order exactly, so on those matrices the least-cost order is a sequence of locally excellent three-step choices. On the other eleven it is not, and the least-cost order there does something no three-step window sees. Reading those eleven orders — whether they take an expensive pivot early to buy short rows later, and how early — is the measurement that would say what a fourth step would have to look for.