Every essay — page 18
Exact arithmetic, and what it costs instead
An integer matrix eliminated over the rationals commits no rounding anywhere, so the forward error is zero, the residual is the zero vector, and the identity the rest of this site is built on has nothing left to say. The cost does not disappear with the error — it moves into the length of the numbers, where three eliminations returning the same integer differ by four orders of magnitude in the widest one they form. What is left to decide is which route pays: divide by the previous pivot and stay in the integers, reduce every fraction and pay a gcd per operation, or work modulo primes where nothing can grow and put the answer back together afterwards.
The answer is longer than the question
An exact solution of an integer system is a vector of fractions, each of them a ratio of two determinants.
How many primes the answer needs
Work modulo a word-sized prime and no intermediate can exceed twenty-six bits, whatever the matrix does.
A prime that divides the answer
A modular elimination reports a singular matrix and is telling the truth — over the field with p elements the matrix is singular.
A fraction recovered from one remainder
A solution over the rationals can be computed modulo a prime power and then recovered — the residue determines the fraction uniquely, but only once the modulus is twice the square of the fraction's longer part.
The rank depends on the ring
A floating-point rank is a decision about a threshold.
What a determinant does not determine
Two integer matrices can have the same determinant, the same rank and the same size, and define genuinely different maps.
A basis that describes its lattice badly
The same set of points has infinitely many bases, they are all correct, and they are not equally useful.
An exact answer to a measured problem
The residual is the zero vector, nothing was rounded at any step, and the answer is wrong in its first digit.
A relation among digits that were not there
A lattice finds the exact integer combination of several numbers that vanishes, and it needs enough digits of them to do it.
Rounding a coordinate in the wrong basis
The nearest lattice point is found by writing the target in the basis and rounding each coordinate, which is three lines of arithmetic and is wrong.
The knob and the rounding
The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect.
A bound on every intermediate at once
Fraction-free elimination's intermediates are minors of the original, which is a theorem about exactness.
Three orders and one last entry
Over the integers there is no stability to pivot for, so a fraction-free elimination swaps rows only when the pivot is zero.
The room a relation has to stand out
A lattice search for an integer relation returns its shortest vector, and the proposal was to return the gap to the next one as well, so a caller could tell a relation from an accident.
Two precisions guard the other edge
Run a lattice relation search at N digits and again at N/10, and accept its answer only if both runs return the same vector.
The pivot is in every product
A fraction-free elimination's intermediates are minors, and Hadamard bounds a minor by the lengths of the rows it is made of — so the rule that picks the smallest pivot entry looked like a proxy for a rule that picks the shortest row.
The digits between the two searches
A lattice relation search run at N digits and again at N/10 never agrees with itself on a relation among the rounding, but it does agree on 62 approximate relations at fifteen digits or fewer — accidents that really are the shortest vector there, and that dropping a digit was said to be unable to dislodge, since a combination that cancels to D digits cancels to D − 1.
What reading the next pivot buys
In a fraction-free elimination every pivot is paid for twice — it multiplies every entry of its own step and divides every entry of the next — and the rule that picks the smallest pivot entry left a median 20 per cent above the least arithmetic any row order reaches.
The field decides it, usually
A matrix whose rank depends on the field it is read over was built, the first time, from its invariant factors outward, because random integer matrices never seemed to show the effect.
An order found once knows what the rows know
Searching for a fraction-free elimination's least-cost row order costs forty to two hundred and sixty times the elimination, so it can only pay if one order serves a whole family.
Every entry under the determinant
The Hermite form's swell was put down to its transform — the record of how the answer was reached — while the form's own entries stayed bounded.
The swell was one-sided
The Smith form can be computed modulo the determinant, and it was predicted to return the right invariant factors, to stay within twice the determinant's width, and to cost about what the modular Hermite form costs instead of the far larger count of the plain Smith routine.
Each column divides by the prime
Square random 0/1 matrices are almost always invertible over the rationals and invertible modulo a small prime only at that field's uniform law — so at twenty rows, 72% of the rationally invertible ones are singular modulo two.
A graph is alternating modulo two
Random 0/1 matrices are invertible modulo two at the uniform law's rate, 0.289, and a random graph's adjacency matrix was predicted to follow the symmetric law instead, about 0.42.