Pairwise summation

In <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a>, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite-<a href="/facts/Arithmetic_precision/RUfYtpgo">precision</a> <a href="/facts/Floating-point/eIckahxe">floating-point</a> numbers that substantially reduces the accumulated <a href="/facts/Round-off_error/aF9N8X4I">round-off error</a> compared to naively accumulating the sum in sequence. Although there are other techniques such as <a href="/facts/Kahan_summation/6a3meV1l">Kahan summation</a> 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 <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursively</a> breaking the sequence into two halves, summing each half, and adding the two sums: a <a href="/facts/Divide_and_conquer_algorithm/pC1X7Ws7">divide and conquer algorithm</a>. Its worst-case roundoff errors grow <a href="/facts/Big_O_notation/weFFjSWg">asymptotically</a> as at most O(ε log n), where ε is the <a href="/facts/Machine_precision/Ujsx0nA5">machine precision</a> (assuming a fixed <a href="/facts/Condition_number/9Tjtk6wh">condition number</a>, as discussed below). 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). <a href="/facts/Kahan_summation/6a3meV1l">Kahan summation</a> has a <a href="/facts/Error_bound/orSvvIMC">worst-case error</a> of roughly O(ε), independent of n, but requires several times more arithmetic operations. If the roundoff errors are random, and in particular have random signs, then they form a <a href="/facts/Random_walk/08v0jmfv">random walk</a> and the error growth is reduced to an average of 
 
 
 
 O
 (
 ε
 
 
 log
 ⁡
 n
 
 
 )
 
 
 {\displaystyle O(\varepsilon {\sqrt {\log n}})}
 
 for pairwise summation.
A very similar recursive structure of summation is found in many <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (FFT) algorithms, and is responsible for the same slow roundoff accumulation of those FFTs.

Pairwise summation open-in-new

Pairwise summation