Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Pairwise summation — where it appears

Adding a vector by splitting it in half, summing each half and adding the two, rather than accumulating in a line. The error then grows like the logarithm of the length instead of like the length, and it is the ordering a parallel reduction produces by accident.

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

051210241536204810⁻¹⁷10⁻¹⁴terms consumederror accumulated so farone accumulator8 piecesthe steps are the partial sumspeak partial sum32the answer1.6·10⁻⁵error, one piece7.6·10⁻¹⁴error, 8 pieces2.4·10⁻¹⁴mean at p = 648.1·10⁻¹⁵the walk sets the sizeand nothing sets the value

Where the disagreement comes from

The error of a reduction is a walk whose step length is the spacing of the running total, not of the answer. That one sentence predicts the size of the disagreement to a factor of two, explains why dividing the work makes it smaller, and explains why the value cannot be predicted at all.

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 accumulationAssociativityGaussian eliminationGram–SchmidtKahan summationRandom walkReduction orderReduction treeRun-to-run variationSummation condition numberSummation errorUnit roundoff

All concepts