An order found once knows what the rows know

What reading the next pivot buys found the least-cost row order of a fraction-free elimination by looking ahead — an elimination whose every intermediate is a minor of the original, as every intermediate is a minor showed, so that its cost is set by how long those minors grow. In a Bareiss elimination over the integers every pivot multiplies every entry of its own step and divides every entry of the next, and with each multiplication charged at the product of its operands’ bit lengths, a rule that reads three pivots ahead reproduces the least of all 40,320 row orders on thirteen of twenty-four 8 × 8 matrices. It also measured the price: the look-ahead’s simulated steps cost forty to two hundred and sixty times the elimination it chooses for. On one matrix the search can never pay for itself.

Its last section asked whether it could pay across many. “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.”

The prediction is right about the matrices it was made on and wrong about families in general. What decides it is a question the prediction did not ask: what made the order best in the first place, and whether the next matrix shares it.

Three families, every order costed #

Each family has twelve members of order 8 with integer entries from $-6$ to $6$, drawn from seeded streams and kept when nonsingular. The first family has independent entries, as the earlier essays’ matrices did. The second shares a pattern of zeros: the same 40 per cent of positions are zero in every member, and the rest independent. The third shares its row scales: row $i$ of every member is multiplied by $2^{s_i}$, with the same scales $s = (4, 0, 3, 3, 3, 0, 1, 3)$ throughout — the kind of family a sequence of systems from one model produces, where each equation keeps its units from one solve to the next.

For every member, every one of the 40,320 row orders is run as a Bareiss elimination and costed. That table holds everything: the least cost and the order that reaches it; the natural order’s cost; the cost of any other member’s least-cost order on this member; and, for each member, the order whose total cost over the other eleven members is least — an order trained on the family and tested on a member it never saw. Two cheap rules from the earlier essays are run beside them: the smallest nonzero pivot entry in the column, and the row norms of the original matrix taken in increasing order.

A reused order is a random order — when nothing is shared #

The figure above is the whole comparison, as the median member’s cost over its own least. On independent entries the natural order costs 1.600 and the median of all 40,320 orders 1.717. Another member’s least-cost order costs 1.540, and the order trained on eleven members 1.458. Neither is the “within a few per cent” the amortisation needed; both are ordinary orders.

The percentile figure says so more directly. Among each member’s 40,320 orders, another member’s best order sits at a median of the 35th percentile on independent entries — better than a typical order, which would sit at the 50th. That is a sampling effect and not a transfer. Rows of an independent-entry matrix are exchangeable, so a fixed order costs a member, on average, exactly what a random order does; and a second independent family of twenty-four members, drawn from other seeds, puts the reused order at a mean of the 47th percentile over 493 pairs. With twelve members a few lucky orders move the median; with twenty-four they do not.

The shared zero pattern does no better. Another member’s best order costs 1.592 and sits at the 31st percentile, and 39 of the 132 reuses cannot be run at all: they meet a zero pivot that the member they were found on did not have. A zero pattern does change which orders are legal — the distinction a prime that divides the answer drew between a pivot that is zero and one that merely looks so — but it says almost nothing about which legal order is cheap, because in a Bareiss elimination the zeros disappear after the first step or two — every later entry is a minor, and minors are rarely zero — while the cost is in the bit lengths those minors grow to.

And transfers completely when the rows carry it #

On the family with shared row scales the natural order costs 1.884 of the least and the median order 1.860 — scaled rows make an arbitrary order dearer than on independent entries, because a row multiplied by sixteen carries four extra bits into every product it touches, and a bound on every intermediate at once is the account of how far those bits can grow. Another member’s least-cost order costs 1.126, at the 1st percentile of the 40,320; the worst of the 132 reuses costs 1.458, which is still cheaper than the natural order on the median member. The trained order costs 1.156. On the dial’s other two families the grid is a patchwork of values between 1.1 and 2.3; on this one almost every cell is pale.

The reason is visible in the orders themselves.

Every member’s least-cost order starts with one of the two unscaled rows, 2 and 6, and ten of the twelve start with both, in one order or the other; most take the row scaled by two third or fourth; and ten put row 1, the one scaled by sixteen, second from last. The scales decide the shape of the order and the entries decide the details within each group of equally scaled rows. A member’s best order is therefore close to every other member’s best order at the level the scales fix, and different only in the details, which cost a few per cent. That is exactly what the reuse grid measures.

The rule that searches nothing wins anyway #

Here the prediction’s reasoning returns, sharpened. The order transfers on the scaled family because the rows’ sizes decide it, and the rows’ sizes are visible. A rule that reads them should do as well as any reused order without having searched.

It does better. On the scaled family the smallest-pivot rule costs a median 1.014 of the least and the norm rule 1.049, against 1.126 for a reused order and 1.156 for a trained one. On the zero-pattern family the smallest-pivot rule costs 1.076 against the reused order’s 1.592. On independent entries it costs 1.240 against 1.540. Member by member, the rule is cheaper than the trained order on 7 of 10 members with independent entries, 9 of 11 with the shared zeros and 10 of 11 with the shared scales — the members missing from each count being those on which the trained order meets a zero pivot. The pivot is in every product found the smallest-pivot rule at 1.165 of the least on its matrices and asked whether anything cheap could close the rest; reusing an order, even one trained on eleven matrices of the same family, is not that thing.

The smallest-pivot rule reads more than the row scales: it reads, at every step, which entry of the current column is shortest, and in a Bareiss elimination that is the entry that will multiply everything at this step and divide everything at the next. A reused order fixes the sequence of rows before the elimination has produced any of the minors whose lengths decide the cost. On the scaled family the two agree about the first few steps, because the scales dominate the first minors’ lengths; later, the rule reads lengths the scales no longer determine, and the reused order cannot.

Where the shared structure is the entries themselves #

The three families above share something a rule can see, or nothing at all. A fourth shares something no rule can see: one base matrix, the same in every member, with two of its sixty-four entries redrawn at random. The members are nearly the same matrix, and the earlier essay’s Still-open question — whether an order found once could be reused — has its most favourable case here.

It is not favourable in the way expected. Another member’s least-cost order costs a median 1.155 of the least on this family, worse than on the scaled family, even though the members differ in two entries and the scaled family’s in all sixty-four. Two redrawn entries are enough to move a member’s least-cost order: of the twelve members’ least-cost orders only one occurs more than once — four members share it — and the other eight are all different, because near the least there are many orders within a few per cent of each other and a small change to the matrix reshuffles which of them comes first. A single member’s best order is a noisy sample of the family’s best.

The order trained on eleven members averages the noise away. It costs a median 1.070 of the least on the member it never saw — and the smallest-pivot rule costs 1.136. On this family, and only on this one, an order found by search and reused beats the rule that reads the matrix. The rule reads the current column’s shortest entry, which is the right thing to read when the rows differ in kind; when every member is the same matrix give or take two entries, what matters is the one ordering that is good for the base matrix, and the rule, reading one column at a time, does not find it. The trained order does, because the base matrix is what the eleven training members have in common.

The percentile figure shows the same thing from the other side. On the family of perturbations a reused order sits at a median of the 2nd percentile of the member’s 40,320 orders — nearly as good, by rank, as on the scaled family — and still costs fifteen per cent over the least. On these matrices the cheapest orders are crowded: on four members of the family the hundredth-best order is four to nine per cent over the best, and the order at the 2nd percentile — about the six-hundred-and-fiftieth — nine to nineteen per cent over, so a reused order that lands there is both excellent by rank and mediocre by cost. The scaled and independent families’ bottoms look the same. Rank and cost tell different stories whenever the bottom of the distribution is flat, which is why the figures report both.

That is the general shape completed. An order found once carries what its family shares. When that is visible in the rows — their scales, their lengths — a rule reads it directly and wins. When it is invisible to any rule, because it is the particular entries of a particular matrix, the trained order is the only way to get it, and it pays: here, seven per cent of the least against the rule’s fourteen. What does not pay, on any family, is one member’s best order taken alone.

What amortising a search would need #

The earlier essay’s look-ahead costs forty to two hundred and sixty eliminations to run, and the exhaustive search that found every least-cost order here costs 40,320. For any of it to pay through reuse, the reused order would have to beat the cheapest rule by enough to recover that cost over the family’s members. One member’s best order, reused, beats the rule on no family. An order trained on eleven members beats it on one family of four — the one whose shared structure is a particular matrix — by seven hundredths of the least, which is a real saving per elimination and would repay the search only over a family of thousands of members.

So the search is not amortised over these families, and the reason is not the one the prediction gave. It is not that orders fail to transfer. On the scaled family an order transfers because something visible in the rows decides it, and a rule that reads the rows gets that something for nothing, and more besides. On the family of perturbations what transfers is invisible to a rule, and there — only there — the trained order is worth having.

That shape is worth stating in general. An optimisation done once and reused across a family carries the family’s shared structure and nothing else, since anything else was particular to the member it was found on. If the shared structure can be observed, a rule that observes it does at least as well as the reuse; if it cannot be observed, the reuse is the only way to get it, and the case in which searching once is worth its price. The answer is longer than the question put a floor under the cost of the output that no ordering can move; every ordering here moves only the part above that floor, and an answer with no error in it is the reminder that over the integers that part is all there is to choose — there is no accuracy to trade for it, only bits.

What the families do not show #

The cost is the schoolbook one, each multiplication charged at the product of its operands’ bit lengths and each exact division at the product of the dividend’s and the divisor’s; a fast multiplication would charge long products less, flatten the differences between orders, and so make every choice above matter less without changing which choice wins. Three families of twelve 8 × 8 members, entries of three bits, a single scaling pattern and a single zero pattern. A family whose shared structure is in the columns — the same columns scaled in every member — would put the structure into every row equally, and a row order could not carry it; the prediction is that there a reused order is a random order again. The family of perturbations was perturbed in two entries; with one, the members would share more, and with eight, less, and the crossover at which the trained order stops beating the rule is not located here. At order 8 the exhaustive search is affordable and the least is known; at order 20 neither is, which is where an amortised search would matter if it ever mattered, and where this measurement cannot follow.

Still open: a family of perturbations, and the columns’ scales #

How many members a trained order needs. On the family of perturbations the trained order used eleven members and beat the rule by seven hundredths. A trained order averages the members’ noise, so its excess over the base matrix’s own best should fall roughly as one over the number of members. The prediction with a sign is that three members already put the trained order below the rule on the median member, and that one member — a single reused order — does not, as measured above.

Scales on the columns instead of the rows. Multiplying column $j$ of every member by $2^{t_j}$ adds $t_j$ bits to every entry in that column, in every row alike, so it changes which column is expensive and not which row is. The prediction is that a reused row order is then a random order — at the 50th percentile, give or take the sampling seen above — while the cost of every order rises by the same few bits, so that the natural order’s ratio to the least is the independent family’s.