Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rational arithmetic — where it appears

Arithmetic on fractions of integers carried out exactly, with numerators and denominators allowed to grow as far as the computation needs. It removes rounding altogether, and in exchange the length of the operands becomes part of the cost of every operation.

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

H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known

An answer that is known

Almost every demonstration of numerical error estimates the error by computing the same thing more carefully. The Hilbert matrix does not need that: its inverse is a closed form in integers, so the true answer is available exactly and the error is measured rather than approximated.

error · Exact ground truth 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 arithmeticBackward errorCertificateDeterminantFloating-pointInteger relationLattice reductionOrthogonality defectRoundingGaussian eliminationGround truthHilbert matrix

All concepts