An answer with no error in it

Every field before this one is about an arithmetic that cannot represent its own answers. A float has fifty-three significand bits, the exact result of almost any operation on two of them does not fit, and the whole apparatus of this site — a backward error saying what the algorithm did, a condition number saying what the problem did to it, and their product being all anybody sees — exists to account for the difference.

There is a class of problems where none of that applies. If a matrix has integer entries and the question is its determinant, its rank, or the solution of a system it defines, then every quantity involved is a rational number, every arithmetic operation on rationals produces a rational, and an elimination performed in them rounds nothing at any step. The forward error is zero. The backward error is zero. The residual is the zero vector, not a small vector. The condition number is a perfectly good number and it multiplies nothing.

So the interesting question is not whether it works. It is what it costs, and the answer is the subject of this field: the cost stops being a count of operations and becomes the length of the numbers those operations are performed on.

The identity, with nothing in it #

The relation the rest of this site reports every measurement against is

forward error  ⪅  condition number × backward error

and the essay that introduced it is careful that both factors are separately measurable. Here the right-hand side is zero because its second factor is, and a product with a zero in it carries no information about the other one. The matrix above has a two-norm condition number of 32.7. That is a true statement about the matrix and it predicts nothing at all about the computed answer, because the computed answer is the answer.

This is not a rhetorical point. It changes what a figure in this field can be. There is no residual badge to print, because ‖PA − LU‖ is a matrix of exact zeros at every size and on every family, and a badge reading 0 on nine consecutive figures tells a reader nothing they did not know from the first. What can be measured is on the vertical axis of the hero: the number of bits in the widest integer the routine had to hold.

Where the cost went #

Take a twelve by twelve matrix whose entries are integers between −9 and 9. Its determinant is 2,269,932,161,262 — twelve digits, forty bits, and small enough to write on a line. Three routes reach it:

• Fraction-free elimination, which stays in the integers by dividing each step by the previous pivot. The widest number it ever forms is 40 bits.
• Elimination over the rationals with every fraction reduced to lowest terms, which reaches 39 bits and calls a greatest common divisor on every entry it forms to stay there.
• Elimination over the rationals without reducing, which is the routine anybody writes first: numerator times numerator, denominator times denominator, subtract with a common denominator. It reaches 1,422,165 bits.

A million and a half bits is four hundred and twenty-eight thousand decimal digits, carried in order to compute a twelve-digit answer. Nothing about that is a rounding error, a stability question or a choice of pivot. All three routes are correct. All three return the identical integer. They differ by a factor of thirty-five thousand in the size of the objects they manipulate, and the flop count — which is the same n³/3 for all three — sees none of it, exactly as the flop count fails to predict the time for a different reason two fields over.

That is the field’s organising fact, and it can be stated in one line: an operation on a forty-thousand-bit integer is not one operation.

Drawn across the sweep, the three routes separate at once and one of them is not even monotone.

Across n = 5, 7, 9, 11, 12 and 13 the determinant needs 15, 24, 25, 33, 40 and 44 bits; fraction-free elimination’s widest intermediate is 15, 24, 25, 35, 40 and 44; the reduced rational route’s is 15, 17, 25, 35, 39 and 44; and the unreduced route’s is 85, 711, 5,947, 341,287, 1,422,165 and 1,120,288.

Bareiss never exceeds the answer by more than two bits at any size, which is the fraction-free guarantee doing exactly what it promises: every intermediate it forms is a minor of the original matrix, so Hadamard’s bound on the answer bounds the workings too. The reduced route is within nine bits either way and is twice narrower than the answer — 17 bits at n = 7 against an answer of 24 — because the widest thing it holds need not be the last thing it computes.

And the unreduced route’s swell is not monotone in the size. It falls from 1,422,165 bits at n = 12 to 1,120,288 at n = 13, on a larger matrix. Nothing is wrong: the widest intermediate depends on which entries happen to share factors, and a different matrix is a different draw. But it means the four-orders-of-magnitude gap this essay is about is a property of a matrix and not a function of n — the growth rate is a law and the value at any size is a sample.

Why the unreduced route explodes, exactly #

The mechanism is worth writing out because it is short and because it is the reason the other two routes exist.

At each elimination step, an entry becomes aᵢⱼ − (aᵢₖ/aₖₖ)·aₖⱼ. Written over a common denominator with no cancellation performed, the new numerator is a product of two previous numerators minus another such product, and the new denominator is a product of two previous denominators. The tempting reading is that the length doubles — one product of two b-bit numbers is 2b bits — and the measurement says it quadruples, which assertTheRationalEntriesQuadruple holds to within 8 per cent over the late steps at n = 10, 14 and 18. The extra factor is the subtraction: it forms aᵢⱼ·(aᵢₖaₖⱼ’s denominator) minus the other product over the product of the two denominators, so four integers are multiplied together and not two, and a step that looks like one multiplication is two.

Nothing cancels unless something is asked to cancel. The fractions are in lowest terms after the last step, in the sense that the determinant comes out as an integer over one; they are simply never put there on the way.

So the obvious repair is to reduce, and it works: the reduced route’s widest intermediate is 39 bits at n = 12, one bit narrower than the fraction-free route’s. What it costs is that every addition, every multiplication and every subtraction is followed by a greatest common divisor of two integers — and a gcd is not a constant-time operation any more than a multiplication of two long integers is. The reduction is exactly the work the unreduced route was avoiding.

That fork — pay in gcds or pay in length — is the first of the field’s three answers, and the second is the one that makes it unnecessary.

The division that is always exact #

Fraction-free elimination performs

aᵢⱼ  ←  (aₖₖ·aᵢⱼ − aᵢₖ·aₖⱼ) / (previous pivot)

and never leaves the integers, because that division is exact at every step of every matrix. It is not exact by luck and it is not exact because of anything about these entries. It is exact because the numerator, before the division, is a determinant with the previous pivot as a factor — which is Sylvester’s identity, and which the next essay in this field checks against the minors themselves rather than quoting.

The consequence for cost is immediate. Each intermediate entry is a minor of the original matrix, so its size is bounded by Hadamard’s bound on a minor of that size, which grows like k·(entry width + log k) — linearly in the step index, not exponentially. That is the flat lower group of curves in the hero, and it is why the fraction-free route needs no gcds: the division that keeps the numbers small is a single exact division rather than a search for a common factor.

How large the answer is allowed to be #

The third route removes growth entirely by removing the room for it: work modulo a prime that fits in a machine word, where no entry can exceed the modulus, and put the answer back together from several such computations by the Chinese remainder theorem.

That only works if the number of primes is known in advance, and it is, because Hadamard’s bound says how large a determinant can be before any of it is computed: |det A| is at most the product of the row two-norms. On the matrix above the bound is 52 bits and the answer occupies 40, so two twenty-six-bit primes suffice and the routine uses two.

The bound is not loose by construction, which matters, because a budget derived from a bound that is never attained would be a budget that is always wrong. On a Sylvester Hadamard matrix of order eight the bound is 25 bits and the determinant occupies 25: the bound is reached. On the Pascal matrix, whose entries reach twenty bits at n = 12 and whose determinant is exactly 1, the bound is 149 bits and the answer is one. Both are correct behaviours of the same inequality, and the second looks like a warning that entry growth during an elimination is not predicted by the size of the answer — which is a claim about intermediates supported by a bound on the answer, and therefore a claim that has to be measured separately.

On the family the figures are drawn on, the growth is the answer exactly #

Hadamard’s bound is a statement about a determinant. The intermediates of a fraction-free elimination are minors, so the bound applies to them too, but the relation between the two is not something the bound settles. Measured — widest bit length Bareiss ever holds against the determinant’s own length:

On the two families every figure in this essay is drawn on, the two columns are equal, at every size. Not bounded by, not proportional to — the same integer. The reason is one line: the last pivot of a fraction-free elimination is the determinant, and on a matrix with no special structure no earlier minor is longer than the whole one. So the widest number the routine ever holds is the answer, and the answer is the smallest thing it could possibly have held.

That also puts Hadamard’s bound in its place. At n = 12 on the random family it says 52 bits and the elimination touches 40; on the wide family it says 133 and the elimination touches 121. The bound is the loose party by 12 bits in both cases, which is a factor of four thousand in the number and about half a prime in the budget.

The claim above does hold, on the other two families, and holding it to a number is better than holding it to a warning. On the Pascal matrix the determinant is exactly 1 and the intermediates reach 2n − 4 bits — 8, 12, 16, 20 at the four sizes, linear in the size and completely unrelated to the answer. On the scaled Hilbert family they run 20 to 50 per cent above the answer’s own length. So entry growth is not predicted by the answer is a statement about structured matrices, and on unstructured ones the prediction is exact.

Where fraction-free is not the cheapest road #

The same measurement has one more thing in it, and it qualifies this essay’s own summary. Reduce and pay in gcds, or do not and pay in length, and fraction-free elimination is the third road that pays neither is true where it was measured: on the random family at n = 12 the reduced rational route holds 39 bits and Bareiss holds 40, so Bareiss gets the reduced route’s length without its gcds and the sentence is a fair account.

On the scaled Hilbert family the reduced route holds 33 bits where Bareiss holds 161 — a factor of 4.9, and it is 33 against 131 for the determinant itself, so the reduced route carries entries narrower than the answer right up to the last multiplication that assembles it. What a gcd removes there is a genuine common factor that the entries of a scaled Hilbert matrix share by construction, and an exact division by the previous pivot cannot see it: Sylvester’s identity divides by the one number it is guaranteed to be able to divide by, not by the largest one available.

So the fork is real and which road is narrowest depends on the family. Fraction-free wins on generic integer data by never calling a gcd, and it is beaten on length — though still not on gcd count — by a route whose fractions share factors. assertTheWidestIntermediateIsTheDeterminantOnPlainEntries holds both halves: the equality on the plain families, the 2n − 4 on Pascal, and the factor of five on Hilbert.

What is the same, and what is not #

Three things this site has said elsewhere survive into the exact setting unchanged.

Two routes to every number. The habit is stronger here rather than weaker: two floating-point routes to a quantity agree to a relative 10⁻¹⁵ and the essays price the last digit, but two exact routes agree or they do not. There is no tolerance in the comparison and nothing to negotiate. The determinant above is checked three ways and the differences are the integer zero.

A rank is still a decision, and now for a different reason. The essay that made that argument made it about a threshold: a floating-point matrix has singular values and no rank, and the rank is where somebody puts a line. Remove the arithmetic error and the threshold goes away — and the answer still is not a property of the array of numbers, because it depends on the ring the entries are read in. That is later in this field and it is a genuinely separate failure, closer to a rank that depends on the thread count than to a threshold.

An exact answer to the wrong problem is still wrong. The whole apparatus of conditioning survives, because it was never about arithmetic. It is about the map from data to answer, and if the data was measured rather than given then the exactness buys nothing at all: the field’s last essay measures a case where an exact solve and a float solve of the same physically-obtained system differ by less than either differs from the truth.

What a float does with a forty-bit answer #

The comparison in that figure is worth reading carefully, because it is the only place in this field where floating point appears at all.

A determinant of 2,269,932,161,262 needs 40 bits. A double has 53, so the answer fits — and the float LU still misses it, by a relative 10⁻¹⁵, because the answer is not what is being held. What is being held is a running product of twelve pivots, each of which is a quotient of quantities that do not fit, and the last digits of that product are the ones the cancellation took. Raise the entries to three digits and the determinant needs 82 bits, at which point no amount of care in the elimination can help, because the destination has 53.

That is the honest boundary of the field. Floating point is not bad at this; it is answering a different question, at a fixed precision, for a fixed price. Exact arithmetic answers the asked question at a price that depends on the answer’s own size — and once that size passes the significand, the two are not competing.

The measurement that changed how this is stated #

The first version of the swell figure plotted the reduced-rational route as the villain, on the strength of the phrase intermediate expression swell, which is what the literature calls this. The measurement refused it. The reduced route sits at 39 bits at n = 12, one bit below the fraction-free route, and at 13 bits at n = 6 where fraction-free is at 16 — narrower than the answer’s own length, because reducing a fraction whose value is small can throw away a great deal.

The swell belongs to the elimination without the gcd, and the two are separate routines that get called by the same name. Stating it as a property of “rational arithmetic” would have been a claim that a five-line change to the inner loop falsifies. What the measurement supports is the fork: the cost is length or it is gcds, and fraction-free elimination is the third road that pays neither.

What this field is for #

Four things are true here that are true nowhere else on this site, and they are why the field exists rather than being a paragraph in the elimination one.

The answer is a certificate. Not a value with an error bar and not a value with a residual — an integer, which either is or is not the determinant, and whose correctness is a statement about arithmetic rather than about a tolerance. The interval-arithmetic essays reach a proved enclosure of a real answer; this reaches the answer.

The cost model is a different one. Everything else on this site counts operations and then argues about where the time actually went — cache, bandwidth, messages. Here the flop count is wrong before any of that, because the operands have lengths, and the length is decided by the algorithm rather than by the machine.

The failure mode is size, not accuracy. A routine here does not return a bad answer; it returns the right one after allocating a gigabyte, or it does not return. That is a different thing to engineer against, and the engineering is Hadamard’s bound and the modular route.

And the ground truth this site has used all along lives here. The Hilbert inverse in closed form, the spanning-tree count from a determinant, the effective resistance as a ratio of two integers: each of those is a float measurement checked against an exact one, and the exact one was computed by the routines this field is about. The instrument has been in use since the collection’s first essays. This is the field that measures the instrument.