Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rational reconstruction — where it appears

Recovering a fraction from its residue modulo m, by running the extended Euclidean algorithm on the pair and stopping it early. The fraction it returns is unique once m exceeds twice the square of the longer of the two parts, and below that the routine returns a different fraction rather than a worse one.

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

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 the same lattice, twicewhat the reduction may not changedet, before1det, after1defect, before7.1defect, after1LLL steps1the determinant is the invariantand the defect is what is being reduced

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. One measurement separates them — the product of the vectors' lengths over the lattice determinant — and the determinant is the invariant the reduction may not change, which is what makes the reduction checkable.

exact · Lattice reduction

Named alongside it

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

Exact arithmeticLatticeBit lengthChinese remainder theoremCramers ruleDeterminantLattice reductionModular arithmeticOrthogonality defectUnimodular

All concepts