Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Error-free transformation — where it appears

A pair of floating-point operations returning both the rounded result and its exact error, so that the two together represent the true value with nothing lost. Two of them carry most of this subject: twoSum for an addition and twoProduct for a multiplication.

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

distinct answersone accumulator303eight pieces72compensated119pre-rounded1exact1worst error 1.17·10⁻⁸worst error 4.61·10⁻⁹worst error 4.96·10⁻¹⁰worst error 4.91·10⁻⁶worst error 0bitwise, or not at allpermutations400one accumulator303pre-rounded1its error4.9·10⁻⁶compensated error5·10⁻¹⁰accuracy and agreement are different propertiesand the accurate one is not the agreed one

The sum that cannot be wrong

Snap every addend to a common multiple before adding, and every partial sum is exact — so the order stops mattering, by construction rather than by luck. Four hundred permutations return one value where an ordinary reduction returns three hundred and three.

machine · reproducible summation 2022242628303210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²k, where the entries are near 2ᵏrelative error of the determinantas writtenfused: exactproducts need 54 bitsone rounding, the whole answertrue determinant1naive, k = 300fused, k = 301first wrong at k27sizes returning 06both forms conformand the source does not say which

One multiply the compiler removed

A determinant whose value is exactly 1, computed as exactly 0 by the expression that is written down, and exactly 1 by the same expression with the multiply and the add fused. Both forms conform to IEEE-754, both are legal compilations of the same source, and nothing in the program says which one you have.

machine · fma contraction

Named alongside it

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

Bitwise reproducibilityCatastrophic cancellationDefiniteness testDeterminantExact accumulationExpression contractionFused multiply-addIEEE 754Kahan summationPre-rounded summationReduction orderReproducible summation

All concepts