Kahan Summation Algorithm - Accuracy

Accuracy

A careful analysis of the errors in compensated summation is needed to appreciate its accuracy characteristics. While it is more accurate than naive summation, it can still give large relative errors for ill-conditioned sums.

Suppose that one is summing n values x_i, for i=1,...,n. The exact sum is:

(computed with infinite precision)

With compensated summation, one instead obtains, where the error is bounded above by:

where ε is the machine precision of the arithmetic being employed (e.g. ε≈10−16 for IEEE standard double precision floating point). Usually, the quantity of interest is the relative error, which is therefore bounded above by:

In the expression for the relative error bound, the fraction Σ|x_i|/|Σx_i| is the condition number of the summation problem. Essentially, the condition number represents the intrinsic sensitivity of the summation problem to errors, regardless of how it is computed. The relative error bound of every (backwards stable) summation method by a fixed algorithm in fixed precision (i.e. not those that use arbitrary precision arithmetic, nor algorithms whose memory and time requirements change based on the data), is proportional to this condition number. An ill-conditioned summation problem is one in which this ratio is large, and in this case even compensated summation can have a large relative error. For example, if the summands x_i are uncorrelated random numbers with zero mean, the sum is a random walk and the condition number will grow proportional to . On the other hand, for random inputs with nonzero mean the condition number asymptotes to a finite constant as . If the inputs are all non-negative, then the condition number is 1.

Given a condition number, the relative error of compensated summation is effectively independent of n. In principle, there is the O(nε2) that grows linearly with n, but in practice this term is effectively zero: since the final result is rounded to a precision ε, the nε2 term rounds to zero unless n is roughly 1/ε or larger. In double precision, this corresponds to an n of roughly 1016, much larger than most sums. So, for a fixed condition number, the errors of compensated summation are effectively O(ε), independent of n.

In comparison, the relative error bound for naive summation (simply adding the numbers in sequence, rounding at each step) grows as multiplied by the condition number. This worst-case error is rarely observed in practice, however, because it only occurs if the rounding errors are all in the same direction. In practice, it is much more likely that the rounding errors have a random sign, with zero mean, so that they form a random walk; in this case, naive summation has a root mean square relative error that grows as multiplied by the condition number. This is still much worse than compensated summation, however. Note, however, that if the sum can be performed in twice the precision, then ε is replaced by ε2 and naive summation has a worst-case error comparable to the O(nε2) term in compensated summation at the original precision.

By the same token, the Σ|x_i| that appears in above is a worst-case bound that occurs only if all the rounding errors have the same sign (and are of maximum possible magnitude). In practice, it is more likely that the errors have random sign, in which case terms in Σ|x_i| are replaced by a random walk—in this case, even for random inputs with zero mean, the error grows only as (ignoring the nε2 term), the same rate the sum grows, canceling the factors when the relative error is computed. So, even for asymptotically ill-conditioned sums, the relative error for compensated summation can often be much smaller than a worst-case analysis might suggest.