Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Orthogonality defect — where it appears

The product of a basis's vector lengths divided by the lattice determinant: one for an orthogonal basis and larger the more skewed the description is. Hadamard's inequality puts a floor of one under it, and in the plane it is how many times too far rounding a coordinate lands from the nearest lattice point.

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

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 10¹110¹skew of the starting basisdistance ÷ the distance to the nearest pointthe nearest lattice pointdashes: the skewed basis's orthogonality defectrounding in the skewed basisrounding in the reduced basisthe same three lines of arithmeticskew40defect there40worst, skewed40mean, skewed26mean, reduced1exact share, skewed0one lattice, one targetand two descriptions

Rounding a coordinate in the wrong basis

The nearest lattice point is found by writing the target in the basis and rounding each coordinate, which is three lines of arithmetic and is wrong. On a basis skewed by forty it lands a mean of 26 times too far and a worst of 40.02 — the basis's own orthogonality defect, to three figures — and the identical three lines on the reduced basis are exact at every target.

exact · Lattice reduction 38434853586368110¹10²10³10⁴e, where the skew is 2ᵉ + 12345orthogonality defect of the basis returneda double holds k exactlyan orthogonal basisthe invariant sees none of itfloat, at 2^521float, at 2^531.4float, at 2^701.2·10⁴residue at 2^701.2·10⁴exact, everywhere1determinant, always1every step was unimodularand the answer is 12,345 times worse

The knob and the rounding

The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect. The one rounding nobody writes down decides everything: above 2⁵³ the reduction returns a basis 12,345 times worse than it should, with the determinant invariant equal to one throughout.

exact · Lattice reduction 4 numbers, coefficients to 30found relations72with a gap of a digit or more54accidents56accidents with that gap05101520253001234decimal digits the numbers are scaled togap, in digitsexact relation foundnot a relationthe room a relation hashorizontal: a gap of one digitdashed vertical: the digits a double has

The room a relation has to stand out

A lattice search for an integer relation returns its shortest vector, and the proposal was to return the gap to the next one as well, so a caller could tell a relation from an accident. Measured, the gap is a certificate with a budget: the digits the numbers really have, shared among all but one of them, less the size of the relation. A found relation's gap sits half a digit under that budget, accidents stay near zero, and a one-digit gap vouches for 81 of 96 relations among three numbers and for 1 of 35 among six. The test numbers the proposal came from turned out to have relations of their own.

exact · Lattice reduction 6 numbers, coefficients to 30relations, both agree34relations, they differ1accidents, both agree5accidents, they differ88510152025300123decimal digits the numbers are scaled togap, in digitsrelation, both agreerelation, they differaccident, both agreeaccident, they differhorizontal: a gap of one digitdashed vertical: the digits a double has

Two precisions guard the other edge

Run a lattice relation search at N digits and again at N/10, and accept its answer only if both runs return the same vector. Among six measured numbers, where the gap between the shortest and next vector vouches for one found relation in 35, the two runs agree on 34. Past a double's sixteen digits they never once agree on an accident, 0 of 561. They do agree on 62 accidents at fifteen digits or fewer — approximate relations that really are the shortest vector there — and the gap, which cannot see a relation among six numbers, can see those.

exact · Lattice reduction

Named alongside it

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

Exact arithmeticLattice reductionDeterminantLatticeUnimodularCertificateFloating pointInteger relationRational arithmeticRoundingBackward errorCatastrophic cancellation

All concepts