In numerical analysis, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite-precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the sum in sequence.
[1] Although there are other techniques such as Kahan summation that typically have even smaller round-off errors, pairwise summation is nearly as good (differing only by a logarithmic factor) while having much lower computational cost—it can be implemented so as to have nearly the same cost (and exactly the same number of arithmetic operations) as naive summation.
In particular, pairwise summation of a sequence of n numbers xn works by recursively breaking the sequence into two halves, summing each half, and adding the two sums: a divide and conquer algorithm.
Its worst-case roundoff errors grow asymptotically as at most O(ε log n), where ε is the machine precision (assuming a fixed condition number, as discussed below).
[1] In comparison, the naive technique of accumulating the sum in sequence (adding each xi one at a time for i = 1, ..., n) has roundoff errors that grow at worst as O(εn).
[1] Kahan summation has a worst-case error of roughly O(ε), independent of n, but requires several times more arithmetic operations.
[2] A very similar recursive structure of summation is found in many fast Fourier transform (FFT) algorithms, and is responsible for the same slow roundoff accumulation of those FFTs.
[2][3] In pseudocode, the pairwise summation algorithm for an array x of length n ≥ 0 can be written: For some sufficiently small N, this algorithm switches to a naive loop-based summation as a base case, whose error bound is O(Nε).
[4] The entire sum has a worst-case error that grows asymptotically as O(ε log n) for large n, for a given condition number (see below).
In an algorithm of this sort (as for divide and conquer algorithms in general[5]), it is desirable to use a larger base case in order to amortize the overhead of the recursion.
[6] The above pairwise algorithm corresponds to b = 2 for every stage except for the last stage which is b = N. Dalton, Wang & Blainey (2014) describe a iterative, "shift-reduce" formulation for pairwise summation.
Essentially, the condition number represents the intrinsic sensitivity of the summation problem to errors, regardless of how it is computed.
[8] 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.
On the other hand, for random inputs with nonzero mean the condition number asymptotes to a finite constant as
In comparison, the relative error bound for naive summation (simply adding the numbers in sequence, rounding at each step) grows as
[1] 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