Work modulo a word-sized prime and no intermediate can exceed twenty-six bits, whatever the matrix does. The catch is that the answer must be reassembled from several such computations, and the number of them has to be fixed before the first one runs — by a theorem about how large a determinant can be, not by trying more until it settles.
The first three essays in this field all had the same shape of problem: exact arithmetic on integers
that grow, with the argument being about how much they grow and whose fault it is. There is a way to
remove the growth entirely, and it is not a cleverer elimination.
Work in a ring where the numbers cannot grow. Choose a prime p below 2²⁶, reduce every entry of the
matrix modulo p, and eliminate. Every quantity that appears is a residue in [0, p), a product of two
of them fits exactly in a double, and there is no bit-length curve to draw because the bit length is
26 from the first step to the last, whatever the matrix was.
Fig. 1 The three exact routes on a matrix with three-digit entries. The modular route’s widest number is
26 bits while the determinant it computes has 82 — because the 82 bits are assembled at the end
rather than carried through the middle.
The answer is then wrong, in a specific and recoverable way: what has been computed is the
determinant of A over the field with p elements, which is det A reduced modulo p. One residue is not
the determinant. Several of them are.
That is a completely different bargain from the two the field has already made. Fraction-free
elimination keeps the intermediates near the answer’s own length and pays for it with a long
division per entry; reduced-rational elimination keeps them there and pays with a greatest common
divisor. Both are still doing arithmetic on numbers whose length is decided by the matrix. This one
fixes the length at twenty-six bits and moves the entire cost into how many times the elimination
is run.
The Chinese remainder theorem says that residues modulo pairwise coprime moduli determine a unique
value modulo their product. So computing det A mod p₁, det A mod p₂, … and combining them recovers
det A modulo p₁p₂…, and once that product exceeds the range det A can lie in, the value is det A.
Two details in that sentence carry all the weight.
The range is signed. A determinant can be negative and the residues cannot, so the reconstruction
has to be read in the symmetric range [−M/2, M/2) rather than in [0, M). Reading it in the wrong one
reports a determinant of −6 as a twenty-digit integer, which is not a small error and is not
detectable from inside: the arithmetic is right, the interpretation is not.
“Once the product exceeds the range” has to be decided in advance. There is no way to look at a
partial reconstruction and tell whether it has settled. Adding a prime always changes the value —
that is what a larger modulus does — and a value that stops changing has not converged, it has
coincided. The number of primes is not something the computation can discover about itself.
That second point is the interesting one, and it is the opposite of how almost every other
computation on this site terminates. An iterative solver stops when its residual is small enough;
the essay on what a method reports is about the gap
between that number and the real one, and the essay on stopping
tests is about two quantities racing to decide it. Every one of
those is a routine watching itself and deciding when to stop. A modular reconstruction cannot watch
itself at all. It has to be told, before it starts, how much work it is going to do.
Hadamard’s inequality supplies the missing number: for any real matrix,
|det A| ≤ Π ‖row i‖₂
the product of the row two-norms. That is computable from the entries in n² operations, before any
elimination, and it says how many bits det A can occupy. Divide by 26 and round up and that is how
many word-sized primes are needed.
Fig. 2 The bound in bits against the determinant’s actual length, on four families. The solid lines are the
budget; the dotted ones are what the budget was for.
On the random family with one-digit entries the bound at n = 12 is 52 bits and the determinant
occupies 40, so three primes are budgeted where two would have done. On the wide family with
three-digit entries the bound at n = 12 is 133 bits and the answer 121: six primes budgeted,
five needed. The waste is small and it is systematic — the bound is a product of row norms and the
determinant is a signed sum with cancellation in it, so the bound exceeds the answer by whatever the
cancellation was.
Why a loose bound would still be the right thing to use #
There is an obvious objection: a bound that is not tight is a bound that makes the routine do more
work than it needs to. It is worth answering carefully, because the answer is not “the waste is
small”.
The alternative to budgeting is checking, and checking is not available. A routine that computed
residues until the reconstruction stopped changing would be reading a coincidence as a convergence.
A routine that computed one extra prime and compared would detect a disagreement rather than a
sufficiency — which is a genuinely useful thing to do, and it is what the next essay is about, but it
tests for a different failure.
So the budget is not a conservative choice among several. It is the only mechanism available, and its
being an over-estimate by a few per cent is the price of the whole route working at all.
It is worth putting that beside the site’s usual complaint about bounds. The growth factor in
Gaussian elimination has a bound of 2ⁿ⁻¹ that no matrix
anybody has ever assembled comes near, and the finding there is that the bound is useless for
deciding anything. The a-priori bound in model
reduction is the other extreme: attained exactly, at
every order, to four decimals. Hadamard’s sits between them and is used differently from either — not
to predict what will happen, and not to reassure, but as an input to the algorithm. A routine that
budgets against a bound is a routine whose correctness depends on the bound being true rather than on
its being tight.
A bound that could never be reached would be a different objection, and this one can be.
Hadamard’s inequality holds with equality exactly when the rows are mutually orthogonal. A Hadamard
matrix — entries ±1, rows orthogonal — attains it: at order eight, every row has norm √8, the product
of the norms is 8⁴ = 4096, and the determinant is 4096. Twenty-five bits budgeted, twenty-five bits
used, nothing wasted.
That is the refusal this essay carries. A claim that the bound is loose by more than a byte on every
matrix is fed the Sylvester construction at order eight and has to reject it — and the assertion is
run rather than described, so the claim in the paragraph above is one the build would catch if it
stopped being true.
Fig. 3 The same measurement at smaller sizes, where the four families have not yet separated and the bound
is within a few bits of the answer on all of them.
The families where it is enormously slack are equally instructive. The unit triangular family has a
determinant of exactly 1 and rows of growing length, so the bound climbs linearly while the answer
stays at one bit. The Pascal family is worse: entries reaching twenty bits, a bound of 149 bits at
n = 12, and a determinant of 1. Both are correct behaviours of the inequality — orthogonal rows are
what make it tight, and neither family has any — and both are the standing reminder that
the size of an answer is not predicted by the size of the entries.
What this buys, measured against the alternatives #
The modular route’s advantage is not speed at these sizes. It is that the cost is a known number of
word-sized eliminations rather than one elimination on operands of unknown length.
Fraction-free elimination performs n³/3 operations on integers that grow to about the determinant’s
length — so the real cost is n³/3 multiplied by the cost of arithmetic at that length, which is
quadratic in it for schoolbook multiplication. The modular route performs k·n³/3 operations on
machine words, where k is the number of primes, and k is itself about the determinant’s length over
26. So the two are the same order and the constants are entirely different, and the second’s inner
loop is a loop over doubles.
The comparison is worth making precisely, because the two routes are the same order and it is easy
to conclude from that that they are the same. Fraction-free elimination performs its n³/3 operations
on operands that reach the determinant’s length L, at a cost quadratic in L for schoolbook
arithmetic, so the total is about n³L²/3. The modular route performs k = L/26 eliminations of n³/3
word operations each, so the total is about n³L/78. The ratio is L, and L is the determinant’s own
bit length — which is the field’s usual answer to everything: the length of the numbers is the cost,
and a route that never lets them get long never pays it.
There is a second advantage that matters more in practice and is invisible in an operation count:
the k eliminations are completely independent. Nothing in the modulo-p₁ computation is needed by the
modulo-p₂ one. The essays about what a machine actually
costs spend their time on data movement and
dependence, and here there is none of either — which is a different kind of statement from a flop
count and is the reason this route is the one that scales.
Fig. 4 Three primes, on a matrix whose determinant needs forty bits. Each of the three eliminations is an
ordinary one on machine words, and none of them knows about the others.
One thing has been assumed throughout and it is not always true: that the elimination modulo p
succeeds. It can fail, and it fails in a way that looks exactly like a correct answer.
If p divides det A then the matrix is singular over the field with p elements. The elimination
reaches a column of zeros, reports a determinant of zero, and is right: that determinant genuinely is
zero. What it is not is a residue of the determinant that was wanted — or rather it is, and it is the
uninformative one, and there is no way to tell from inside a single residue whether the answer is
zero because the matrix is singular or because the prime was unfortunate.
The same substitution reaches the rank. Rank over the field with p elements is a perfectly good
quantity, computed by the same elimination with no threshold anywhere, and it is not the rank over
the rationals — a second and quite separate way for an exact answer to answer a question nobody
asked. Rank as a threshold decision is the floating-point version of
the same trouble reached from the opposite direction, and the two have nothing in common but the
symptom.
That is the whole cost of having no growth, and it is the next essay. It is a failure mode with no
analogue in floating point: nothing in the arithmetic is inaccurate, no quantity is small enough to
be mistaken for zero, and the essay about deciding that a zero has
arrived is about a judgement that here is not being made.
The zero is exact. It is the question that was substituted.
Fig. 5 A matrix whose determinant is 30030 = 2·3·5·7·11·13, and its residue at twenty-five small primes. The
five dots on the floor are correct computations of the wrong thing.
Three properties are wanted of the moduli and only one of them is obvious.
They must be pairwise coprime, which for distinct primes is free. Using a composite modulus is
the failure this reaches for: the modular inverse of a nonzero entry may not exist, the elimination
reports a singular matrix, and the report is about the modulus rather than about the matrix. A list
of primes typed by hand is a place for a composite to hide, so the list here is generated by trial
division rather than written down.
They must be small enough that a product of two residues is exact in the arithmetic doing the
work. A double holds integers exactly to 2⁵³, so a modulus below 2²⁶·⁵ keeps every product inside
it. That is the whole reason for the twenty-six: it is not a word size, it is half a significand.
The same routine written for 64-bit integers would use 31-bit primes and the same argument.
And they must be large enough that not many are needed, which is the counter-pressure. Every
prime is a full elimination, so halving the modulus doubles the work. Twenty-six bits is where those
two meet on a machine whose fast arithmetic is floating point — which is a slightly startling place
for an exact algorithm to end up, and it is the same observation
the low-precision essays make from the other
direction: the fastest arithmetic on a modern machine is the one with the shortest operands, and an
algorithm that wants speed goes to meet it.
Two things about this route are not settled by the budget and both get their own essay.
The first is the unlucky prime: a modulus dividing the determinant, at which the elimination is
correct and uninformative. The defence is to compute more residues than the bound requires and check
that the extra ones agree — which is a genuinely different test from the sufficiency the budget
provides, and which turns an undetectable wrong answer into a detected one.
The second is that everything above is about a determinant, which is a single integer. A solution
is a vector of fractions, and the Chinese remainder theorem reconstructs integers. Getting a fraction
back out of a residue is a separate mechanism with a separate bound, and the bound is about a lattice
rather than about a product of primes.
Fig. 6 The other bound: below a modulus twice the square of the fraction’s longer part, a residue does not
determine the fraction at all, and the failure is a cliff rather than a slope.
Fig. 7 Out to n = 13, where the wide family needs six primes and the unit triangular family’s bound has
passed a hundred bits for an answer of one.Fig. 8 And at the smallest sizes, where one prime does for every family.Fig. 9 A determinant of 1, budgeted at 149 bits, which is the slackest the bound gets on this site.Fig. 10 The case where the bound is attained: rows orthogonal, twenty-five bits budgeted and twenty-five
used.Fig. 11 The integer Hilbert matrix, where the float route has already lost the answer and the modular one has
not noticed the conditioning at all.Fig. 12 The growth this route removes, on the same family.Fig. 13 And on one-digit entries, where the unreduced route reaches 1.4 million bits and the modular one
stays at twenty-six.Fig. 14 The same failure swept further out, where the floor fills slowly and never empties.Fig. 15 The answer’s own length, which is what the budget is a bound on.Fig. 16 The route that carries the length through the middle instead of assembling it at the end.Fig. 17 The float determinant, whose error this route does not have and whose speed it does not match.Fig. 18 The elimination field’s bound that is never attained, beside one that is.Fig. 19 Eight by eight, where the random family needs two primes and the wide one four.Fig. 20 Ten, where the unit triangular bound has passed eighty bits for an answer of one.Fig. 21 A determinant of 1 with a budget of eighty bits, which is what a bound costs.Fig. 22 One prime, on a matrix whose determinant fits inside a single modulus.Fig. 23 The growth the modular route removes, on the ill-conditioned family.Fig. 24 The route that carries the length rather than assembling it.Fig. 25 A map with every invariant factor 1, so no prime is unlucky for it.Fig. 26 The answer this budget is ultimately a bound on.Fig. 27 The rank, where a prime dividing an invariant factor costs one.Fig. 28 And whether the exact answer the budget buys is the answer that was wanted.Fig. 29 Six by six, where every family fits inside one prime.Fig. 30 Eleven, where the wide family needs five.Fig. 31 The attained case, twenty-five bits budgeted and twenty-five used.Fig. 32 And the slackest, a determinant of one under an eighty-bit budget.Fig. 33 The route that carries the length instead of budgeting for it.Fig. 34 A family whose entries are long and whose answer is one.Fig. 35 The invariant factors, which say which primes must be avoided.Fig. 36 The lattice the second stage of the modular route reduces.