Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Lattice — where it appears

The set of integer combinations of a set of vectors, together with the vectors that generate it. Two bases describe the same lattice exactly when they differ by a unimodular transformation, so the volume of the fundamental cell is an invariant of the lattice and the shape of the basis is not.

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 s10 bitss20 bitss30 bitss40 bitss514 bitsinvariant factors, in bitstwo routes, and a conserved quantitydet A-2.3·10⁴Π invariants2.3·10⁴SNF widest15HNF widest24det of the transform-1an algorithm and a definitionagreeing as integers

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. What separates them is a list of integers each dividing the next — computed here twice, once by unimodular elimination and once from the gcds of every minor, which share no algorithm at all.

exact · Normal forms 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 arithmeticDeterminantRational reconstructionUnimodularBit lengthChinese remainder theoremCramers ruleHermite normal formInvariant factorsLattice reductionModular arithmeticOrthogonality defect

All concepts