Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Kahan summation — where it appears

Compensated summation: the part of each addend the running total could not hold is carried and put back on the next step. The error stops growing with the number of terms, which makes it the most accurate summation per operation on this site — and its answer still depends on the order.

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

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 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 02468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸binary64 operations per elementrelative errorruntime orderfixed partitionpre-rounded, one passpre-rounded, two passescompensated (Kahan)exact accumulationwhat determinism costsreproducible policies3cheapest, ops/element3its error2.3·10⁻⁷two passes10⁻¹⁷ordinary, 8 pieces2.7·10⁻¹¹nothing is cheap and exactthe middle of the figure is the answer

What determinism costs

Six ways to add up a vector, priced in operations per element and in accuracy. Nothing sits in the bottom left of the figure — an answer that is the same on every machine costs between three and twelve operations where an answer that is not costs one.

machine · Reproducible summation 02468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²binary64 operations per elementrelative errorruntime orderfixed partitionpre-rounded, one passpre-rounded, two passescompensated (Kahan)exact accumulationwhat determinism costsreproducible policies3cheapest, ops/element3its error0.0024two passes10⁻¹⁷ordinary, 8 pieces3.6·10⁻⁷nothing is cheap and exactthe middle of the figure is the answer

Accuracy and agreement are different properties

The most accurate policy on this site's summation figure returns 119 different answers, and the one that returns a single answer is four orders less accurate. Neither property implies the other, and the vocabulary has one word for both.

machine · Reproducible 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.

Bitwise reproducibilityExact accumulationPre-rounded summationReproducible summationPairwise summationReduction orderUnit roundoffAssociativityBackward stabilityCatastrophic cancellationCondition numberData movement

All concepts