The pivot is in every product

Three orders and one last entry established what a pivot order can and cannot do to a fraction-free elimination. Bareiss’s algorithm eliminates an integer matrix without fractions by dividing every update exactly by the previous pivot, and every number it holds is a minor of the original matrix, which every intermediate is a minor checked against the minors themselves. The last entry is the determinant, so no pivot order can move the peak of the bit-length profile. What an order can move is the middle. On twenty 10 × 10 matrices with entries in ±6, the rule that chooses the smallest nonzero pivot kept the area under the profile of widest intermediate against step lowest, the largest-pivot rule highest, and the spread between them was seven per cent.

The essay offered a mechanism and left it untested. A bound on every intermediate at once had shown that Hadamard’s inequality bounds each minor by the product of the lengths of the rows it is built from. So the rule that should keep the minors small is the one that uses short rows first — the smallest pivot entry was, on this reading, a proxy for a short row. The essay asked four things: whether the row-norm rule does better than its proxy; whether matrices whose rows differ in length separate the rules further; whether an exhaustive search over row orders finds much more room than the rules use; and whether a few per cent of area is worth anything in time, given that multiplying two integers costs more than linearly in their lengths.

All four have answers, and the fourth changes what the first one means.

Two rules that read the row #

The shortest-row rule is measured in two forms. The first chooses, among the rows with a nonzero entry in the pivot column, the one whose original length — the Euclidean norm of the row as the matrix was given — is least. That is the rule the mechanism literally asks for, because the minors at step $k$ are built from original rows. The second chooses by the length of the row as it stands in the partly eliminated matrix, which is what a code could compute cheaply at every step and which reflects what has happened to the row so far. Beside them are the three rules the earlier essay measured: the natural order, which swaps only at a zero pivot; the largest pivot entry; and the smallest nonzero pivot entry.

Every rule is scored two ways. The area is the earlier essay’s: the sum over the steps of the widest intermediate, in bits. The cost is new: the sum, over every multiplication and division the elimination performs, of the product of its two operands’ bit lengths. That is the schoolbook cost of integer arithmetic, and for integers of tens of bits — these reach 29 at n = 10 and over a hundred with spread rows — schoolbook multiplication is what an implementation actually runs.

The same area, a different cost #

The profile the earlier essay drew is the starting point: three rules, three sequences of minors, one peak. Over the same twenty matrices the medians of each rule’s area, divided by the natural order’s on the same matrix, are 1.037 for the largest pivot, 0.969 for the smallest pivot, 0.966 for the shortest original row and 0.964 for the shortest current row. The three rules that choose something small agree to within half a per cent. On area, the mechanism’s rule is its proxy.

The costs do not agree. The smallest pivot costs 0.704 of the natural order’s arithmetic, the shortest current row 0.760, the shortest original row 0.841, and the largest pivot 1.293. The rule the mechanism asked for saves half what its supposed proxy saves. And every one of these cost differences is far larger than the area differences it goes with: three per cent less area under the smallest-pivot rule is thirty per cent less arithmetic. The earlier essay’s warning — seven per cent of the area is not seven per cent of the time — is right, and in the direction that makes the choice of rule matter more than the profile suggested.

Where the cost is #

A Bareiss update of entry $(i, j)$ at step $k$ computes

$$a_{ij} \leftarrow \frac{a_{kk}\, a_{ij} - a_{ik}\, a_{kj}}{p},$$

where $p$ is the previous pivot. It is three products: the pivot times the entry, two other entries times each other, and a division of the difference by the previous pivot. Two of the three involve a pivot.

Under the natural order the three parts are 0.285, 0.288 and 0.430 of the whole. The division is the largest part, because its numerator is the longest number in the step — a product of two entries — and its divisor is the pivot of the step before. The smallest-pivot rule cuts all three, but the pivot’s two parts most: the pivot product to 0.208 and the division to 0.266, where the cross product falls only to 0.226. The shortest original row cuts the division to 0.358 and the pivot product to 0.240.

That is the whole difference. The row-length rule keeps the minors short, as Hadamard promised, and the area shows it. But the cost of a step is not the length of its minors alone. It is dominated by one particular minor — the pivot — which appears as an operand in one product per entry of the step and as the divisor in one division per entry of the next. A rule that makes the pivot small makes those operations — two of every three in the elimination — cheap. A rule that makes the row short makes the pivot small only as often as a short row has a small entry in the pivot column, and on matrices with entries in ±6 that is not often enough.

Rows that differ in length #

The earlier essay predicted that a matrix whose rows differ widely in length gives any rule more to work with. The measurement multiplies each row of the same ±6 matrices by $2^s$, with $s$ drawn uniformly from zero up to a stated spread.

The prediction holds, and more strongly for cost than for area. At a spread of 4 the smallest pivot’s area is 0.896 and its cost 0.510; at 8, 0.846 and 0.449; at 16, 0.827 and 0.389. The largest-pivot rule goes the other way, to an area of 1.105 and a cost of 1.679 at a spread of 16. And the three small rules converge: from a spread of 4 on they agree to within a few hundredths on both measures, because when the rows differ by factors of sixteen and more, the row with the smallest pivot entry and the shortest row are nearly always the same row. The difference between the pivot and the row that the ±6 matrices showed is a difference that only exists when the rows are all about the same length.

The peak does not move under any of it. At every spread every rule reaches the same widest intermediate, because it is the determinant, as the earlier essay’s theorem requires.

The integer Hilbert matrix #

The family the earlier essay named, the Hilbert matrix scaled by the least common multiple of its denominators, is the extreme case of rows that differ: its first row holds the largest entries and its last the smallest, in a smooth progression.

On it the smallest pivot, the shortest original row and the shortest current row choose the same row at every step at every size, which is the convergence of the spread measurement carried to its end. The smallest pivot’s area is 0.835 to 0.903 of the natural order’s and its cost 0.570 to 0.662. The largest pivot’s is within four per cent of the natural order’s on both, because on this matrix the natural order already takes the largest entries first.

How much room there is #

At n = 8 every row order can be run, so the least area and the least cost any order reaches are numbers. The least-area order is 6.4 per cent below the median order, and the rules sit close to it: the smallest pivot’s area is 1.045 times the least, the shortest current row’s 1.033, the natural order’s 1.052. The area has little room in it, and the rules use most of what there is.

The cost has a great deal of room. The least-cost order is far below the natural order — the natural order costs 1.748 times it, the largest pivot 2.419 times — and the smallest-pivot rule reaches 1.165. The shortest original row reaches 1.566 and the shortest current row 1.401. So the smallest-pivot rule recovers about four fifths of the arithmetic the natural order wastes, and the row-length rules less than half of it. The rule that reads one entry per row is closer to the exhaustive optimum of cost than the rules that read whole rows, and the reason is the one above: the cost is in the pivot’s products, and only one rule looks at the pivot.

This is the same instrument the least fill there is used for sparse elimination — every order searched, the heuristic placed against the true optimum — and it gives a similar verdict: the cheap local rule is near the optimum on the quantity it reads, and the question is whether it reads the quantity that costs.

One matrix, forty thousand orders #

The medians hide how the pieces sit on a single matrix, and one of the twelve is worth reading in full. On the first, the least area any of the 40,320 row orders reaches is 88 bit-steps, the median order’s is 94 and the worst order’s 98 — the whole of the area’s range is a tenth of its size. The natural order sits at 95, the largest pivot at 96, the smallest pivot and the shortest current row at 92, the shortest original row at 93. Every rule is within a few bit-steps of every other, and of the best.

The same matrix’s costs spread much wider. The least-cost order does 10,387 bit-products. The natural order does 19,298, nearly twice as many; the largest pivot 21,098. The smallest pivot does 11,623, twelve per cent above the least. The shortest current row does 15,843 and the shortest original row 18,179, which is barely better than doing nothing. Four rules that are indistinguishable on the profile are spread over a factor of two in the arithmetic, and the one that reads the pivot entry is the one near the bottom.

That is the pattern of the medians made concrete, and it answers the earlier essay’s third question in a form it did not anticipate. Its worry was that seven per cent of area might be most of what is available or a small part of it. On area, the rules already take most of what there is. On cost, there was never only seven per cent to take.

Why the division is exact, and what it costs to keep it #

It is worth recalling why the algorithm divides at all, because the division is the largest part of the bill. Eliminate an integer matrix without dividing and each step multiplies the entries’ lengths by about two, so the intermediates double in length at every step: exponential swell, which is what the fraction-free method exists to avoid. Bareiss’s division by the previous pivot is exact — the numerator is a determinant with that pivot as a factor, Sylvester’s identity — and removes exactly the common factor the undivided update would have carried forward. An answer with no error in it measured the swell rational arithmetic suffers when nothing removes common factors; Bareiss removes them by construction, at the price of one long division per entry per step.

So the division is not overhead that a better rule could skip. It is the step that keeps every other step cheap, and its cost is the length of the numerator times the length of the previous pivot. A small previous pivot makes that division short — which is the second place the smallest-pivot rule is paid for, and the one the row-length rules only reach when a short row happens to have a small pivot entry.

What a pivot rule is for, over the integers #

Over the floating-point numbers a pivot rule is chosen for stability, and the largest entry is right because a large pivot keeps the multipliers small. Over the integers there is no rounding, so there is nothing for a large pivot to protect, and the earlier essay measured the natural order and the largest pivot as the two worst rules for length. This measurement adds the cost, and the verdict is the same with more force: the largest pivot is the most expensive rule on every family here — by 29 to 68 per cent over the natural order on the random families, and by a few per cent on the Hilbert matrix, where the natural order already takes the largest entries first — and the smallest pivot the cheapest, by 30 to 61 per cent under it.

It is worth being exact about what that does and does not change. The answer is the same integer under every rule — the determinant, and every solution component, which the answer is longer than the question showed is a ratio of two determinants that no order can move. The largest intermediate is the same. What changes is the work done on the way, and by a margin that for a code eliminating many integer matrices is up to a factor of two and a half in arithmetic for a one-line change in which row is chosen. A floating-point habit carried into exact arithmetic costs that factor for no benefit at all.

How many primes the answer needs measured the other way to keep the lengths bounded — work modulo word-sized primes and reconstruct — where no intermediate exceeds a word whatever the order. That route makes the pivot rule irrelevant to cost by making every number the same length. Within fraction-free elimination, the pivot rule is the only lever there is.

What this does not settle #

Schoolbook cost is the right model for the sizes here, tens to a hundred-odd bits, and the wrong one for integers of thousands of bits, where a subquadratic multiplication changes the balance between long and short operands. The ranking of rules would survive, since shorter operands are cheaper under any model, but the size of the savings would not.

Random ±6 matrices, row-scaled versions of them and one structured family. A matrix whose short rows have large entries in the pivot column — short in norm because they are sparse, say — would separate the smallest pivot from the shortest row in the other direction, and is not tried.

The cost is a count of bit-products, not a time. It is the quantity a time would be proportional to in a schoolbook implementation, and it is measured exactly; a wall-clock measurement on this machine would add nothing but noise.

Still open: a rule for the pivot and the next pivot, and where the division goes #

A rule that reads two pivots. 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 — a two-step rule of the kind one step ahead is one step short measured for growth in floating point — 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.

Division that is not paid for. Bareiss divides every entry by the previous pivot because the division is exact and keeps the numbers from compounding. A variant that postpones the division — accumulating the pivots and dividing once every few steps — trades longer intermediates for fewer divisions. Whether any postponement is cheaper under a schoolbook model, given that the division is already the largest share of the cost, is a question this measurement has made precise and not answered.