Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Chinese remainder theorem — where it appears

The statement that residues modulo pairwise coprime moduli determine a unique value modulo their product. It is how a modular computation reassembles an integer it never held, and it requires the number of moduli to be fixed in advance, because a partial reconstruction gives no sign of whether it is finished.

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

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 2^18modulus, as a power of twoa lattice with one short vectornumerator355denominator1132·max(n, d)², bits18first recovered at18moduli tried42below the bound there are two answersand the algorithm cannot prefer one

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. Below that there is no partial credit: the algorithm returns a different fraction with the same residue, and it is a perfectly good one.

exact · Modular lift

Named alongside it

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

Exact arithmeticModular arithmeticBit lengthDeterminantHadamard boundCramers ruleFraction-free eliminationLatticeRank is a decisionRational reconstructionUnlucky prime

All concepts