Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Hadamard bound — where it appears

The inequality that the absolute determinant of a matrix is at most the product of its row two-norms, with equality exactly when the rows are orthogonal. It is what an exact routine budgets against: it says how many bits a determinant can occupy before any of it is computed, and therefore how many primes a modular route will need.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

3456789101112110¹10²10³10⁴10⁵10⁶nwidest intermediate, in bitsrationals, not reducedfraction-free · rationals reduced · the answerone answer, three widthsn12answer40Hadamard bound52fraction-free40reduced rationals39unreduced1.4·10⁶the error is zero on every curvethe cost is the length of the numbers

An answer with no error in it

An integer matrix eliminated over the rationals rounds nothing, so the forward error is zero, the residual is the zero vector, and the identity this site is built on has no terms left. The cost does not vanish with the error. It moves into the length of the numbers, where three correct routes differ by four orders of magnitude.

exact · Exact cost 1-2-6-7-474-26-12-5-8-524-394151435A, the matrix as given1-2-6-7-401840552700112217207003943011710017279153after 2 fraction-free steps3 × 3 minors25 divisions, all exactthe intermediates are minorswhich is why the divisions come out whole

Every intermediate is a minor

Fraction-free elimination divides by the previous pivot at every step and the division is always exact. Not usually, not for these entries — always, because the number being divided is a determinant with that pivot as a factor, which is a theorem and is checked here against the minors themselves.

exact · Fraction-free 3456789101110²10³nbitsthe answerthe question · det Abits in, bits outn11question484answer729det A33widest part37the answer is the floorand no route writes it down more cheaply

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. So the output carries 2n long integers where the input carried n² short ones, and no algorithm can write it down more cheaply — the length of the answer is a floor under every exact solver rather than a property of one.

exact · Exact cost 34567891011110¹10²nbitsthe budget and what it buysrandom, bound47random, actual33primes needed2Hadamard n = 8, bound13Hadamard n = 8, actual13the count is decided by a theorembefore any arithmetic happens

How many primes the answer needs

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.

exact · Modular lift det mod p, as a fraction of p3713a prime that divides the answerdet A3·10⁴primes swept25unlucky5rate0.2det, in bits15singular mod p is not singularand one residue cannot tell them apart

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. Over the rationals it is not. Nothing in the residue distinguishes the two cases, no quantity is small enough to be suspicious, and the wrong answer is a correct computation of a different question.

exact · Modular lift

Named alongside it

The objects these essays reach for when they reach for this one.

Exact arithmeticBit lengthDeterminantFraction-free eliminationChinese remainder theoremModular arithmeticBackward errorCondition numberCramers ruleExact ground truthIntermediate expression swellMinor

All concepts