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 3 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 24 bits, κ² 10⁶one-pass ÷ κ²u7.7compensated ÷ κ²u0.92Welford ÷ κu0.067two-pass, in u6.5110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10¹⁶κ² = 1 + mean² ÷ variancerelative error ÷ uevery digit goneκ²uone-passcompensated or pairwiseWelfordshifted by x₁two-passdashed purple: κ²u, the digits-lost rulethe formula sets the power of κ

The formula sets the power, the sum sets the constant

The one-pass variance was found losing three to sixty-nine times more than the digits-lost rule allows, and the explanation offered — operands built from a thousand roundings — was never priced. Measured against the exact variance of the stored data, the rule's ratio is the variance's own condition number squared, and the formula decides what power of it the error grows with: two for every one-pass variant, one for Welford's update, none for two passes or a shift. The summation decides only the constant in front — about 0.4√n for running sums, one for pairwise or compensated ones — and the sixty-nine was neither: it belonged to the random numbers.

arithmetic · Cancellation

Named alongside it

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

Error accumulationKahan summationSummation condition numberUnit roundoffAssociativityCatastrophic cancellationCondition numberGaussian eliminationGram–SchmidtRandom walkReduction orderReduction tree

All concepts