Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Lattice reduction — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · exact
  2. 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.

    part 2 · exact
  3. 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.

    part 3 · exact
  4. 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.

    part 4 · exact
  5. 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.

    part 5 · exact
  6. 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.

    part 6 · exact
  7. pooled over every settingaccidents, one digit apart62accidents, three digits apart5relations lost on the way109110¹10²10³digits between the two searchesruns123relations keptaccidents acceptedlogarithmic vertical axiseach digit apart divides the accidents by three or four

    The digits between the two searches

    A lattice relation search run at N digits and again at N/10 never agrees with itself on a relation among the rounding, but it does agree on 62 approximate relations at fifteen digits or fewer — accidents that really are the shortest vector there, and that dropping a digit was said to be unable to dislodge, since a combination that cancels to D digits cancels to D − 1. It cancels, but it stops being the shortest. Two digits apart the accepted accidents fall to 17 and three digits apart to 5, while the relations kept fall from 711 of 755 to 652 and 602 — every one of the losses at fifteen digits or fewer. Past a double's sixteen digits the separation costs nothing and buys nothing.

    part 7 · exact

All series