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 3 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 4914192429343900.20.40.60.81decimal digits of the numbers the lattice is givenshare of trials recovering the relationa double has about this many digitsnumbers that are exactthe same numbers, measureda window with two edgescoefficients up to30exact, at 12 digits1exact, at 401doubles, at 121doubles, at 250doubles, at 400.13one edge is the relationand the other is the data

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. Give it more digits than the numbers have and it finds a relation anyway — among the rounding, with the same confidence and no warning. Recovery runs 8 of 8 at twelve digits and 1 of 8 at forty.

exact · Lattice reduction

Named alongside it

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

Exact arithmeticLatticeLattice reductionBit lengthChinese remainder theoremCramers ruleDeterminantInteger relationModular arithmeticOrthogonality defectRank is a decisionUnimodular

All concepts