Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Associativity — where it appears

The property that (a + b) + c and a + (b + c) are the same number, which holds for real numbers without exception and fails for floating-point ones. Almost everything about how a summation is organised — a tree, a sort, a division across workers — matters only because of that failure.

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

110¹10⁻¹¹10⁻⁸10⁻⁵pieces the vector was divided intodistance from the exact sum, relativethe published boundκ · uone vector, one algorithmdistinct answers21runs26spread, in ulps2.3·10⁷κ of the sum10⁸bound ÷ worst error2.6·10⁴nobody chose pand no answer is the answer

The same program, twice

One vector of 4,096 numbers, one summation algorithm, one precision, twenty-six runs — and twenty-one different answers. Nothing in the program chose between them, every one of them satisfies the textbook bound, and the exactly rounded answer is not among them.

machine · reduction order 10¹10²10³10⁴10⁵10⁶10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹number of terms addedrelative error against the exact sumin orderin a treecompensatedbinary32 · terms are 1/icompensated: 3·10⁻⁸

The order they are added in

Addition is associative in the algebra and is not associative in the arithmetic. The same million numbers, added in a different order, give answers that differ in the third significant figure — and the fix is not a wider float, it is a different order.

arithmetic · summation

Named alongside it

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

Error accumulationGaussian eliminationGram–SchmidtKahan summationPairwise summationReduction orderReduction treeRun-to-run variationSummationSummation condition numberSummation errorUnit roundoff

All concepts