PairwiseSummation - Maple Help

MathematicalFunctions[Evalf]

 PairwiseSummation
 perform a summation using a pairwise algorithm, known to substantially reduce the accumulated round-off error when adding floating-point numbers if compared with adding them one at a time

 Calling Sequence PairwiseSummation(U) PairwiseSummation(U, m, n)

Parameters

 U - one-dimensional Array or procedure of one argument m - (optional) indicates the lower summation limit n - (optional) indicates the upper summation limit

Description

 • The PairwiseSummation command performs a summation using a pairwise algorithm, known to substantially reduce the accumulated round-off error when adding floating-point numbers if compared with adding them one at a time. Although there exist other techniques that can have even smaller round-off errors, pairwise summation provides sufficient advantage while having a much lower computational cost than slightly better algorithms.
 • The first argument, U, is expected to be either a one-dimensional Array or a procedure of one single argument - say $j$ - such that $U\left(j\right)$ gives the ${j}^{\mathrm{th}}$ term to be added. When U is an Array, if the (optional) summation limits m and n where not indicated, the Array dimensions (as returned by the ArrayDims command) are taken for summation limits. If however U is a procedure, the values of m and n should be indicated.
 • When the value of Digits is smaller or equal to the value of evalhf(Digits) and provided that the procedure or Array U satisfy required conditions (see evalhf), the pairwise summation is performed under evalhf, that is using the floating-point hardware of the underlying system and done in double precision. This can significantly speed up the summation process. Otherwise, the summation is performed anyway using option hfloat.

Examples

 Initialization: Load the package and set the display of special functions in output to typeset mathematical notation (textbook notation):
 > $\mathrm{with}\left(\mathrm{MathematicalFunctions}:-\mathrm{Evalf}\right);\mathrm{Typesetting}:-\mathrm{EnableTypesetRule}\left(\mathrm{Typesetting}:-\mathrm{SpecialFunctionRules}\right):$
 $\left\{{\mathrm{Add}}{,}{\mathrm{Evalb}}{,}{\mathrm{Zoom}}{,}{\mathrm{QuadrantNumbers}}{,}{\mathrm{Singularities}}{,}{\mathrm{GenerateRecurrence}}{,}{\mathrm{PairwiseSummation}}\right\}$ (1)

Set the value of Digits to 15 and create an Array with 40,000 random complex numbers, organized into four Arrays, with 1/4 of these numbers in each of the four quadrants of the complex plane, and with all the numbers having absolute value in between 1/10000 and 1/2 - see QuadrantNumbers

 > $\mathrm{Digits}≔15$
 ${\mathrm{Digits}}{≔}{15}$ (2)
 >
 ${A}{≔}\left[\begin{array}{c}{\mathrm{1..4 x 1..10001}}{\mathrm{Array}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{rectangular}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (3)

Concatenate the four Arrays into one containing the 40,000 numbers

 > $B≔\mathrm{ArrayTools}:-\mathrm{Concatenate}\left(2,{A}_{1},{A}_{2},{A}_{3},{A}_{4}\right)$
 ${B}{≔}\left[\begin{array}{c}{\mathrm{1 .. 40004}}{\mathrm{Array}}\\ {\mathrm{Data Type:}}{\mathrm{anything}}\\ {\mathrm{Storage:}}{\mathrm{rectangular}}\\ {\mathrm{Order:}}{\mathrm{Fortran_order}}\end{array}\right]$ (4)

Add now these numbers, using both the standard Maple add command and the PairwiseSummation command: compare the precision (higher with PairwiseSummation) and also the time consumed to perform the summations

 > $\mathrm{_t0}≔\mathrm{time}\left(\right):$$\mathrm{add}\left(B\right);$$\mathrm{time consumed}=\mathrm{time}\left(\right)-\mathrm{_t0}$
 ${8.63950358284711}{-}{38.2988008918779}{}{I}$
 ${\mathrm{time consumed}}{=}{0.093}$ (5)
 > $\mathrm{_t0}≔\mathrm{time}\left(\right):$$\mathrm{PairwiseSummation}\left(B\right);$$\mathrm{time consumed}=\mathrm{time}\left(\right)-\mathrm{_t0}$
 ${8.63950358331158}{-}{38.2988008918301}{}{I}$
 ${\mathrm{time consumed}}{=}{0.047}$ (6)

Note that, depending on the random sample of numbers, the difference in time consumed for adding 40,000 complex numbers is either advantageous for PairwiseSummation or negligible, due to performing the pairwise summation under evalhf. Now, we know from the theory [1] that the pairwise summation result has less round-off error but how could we verify that? By performing the same addition with a higher value of Digits in order to diminish the accumulation of round-off error. For instance, perform the addition with Digits = 20, then round the result to Digits = 15 and compare with the results (5) and (6):

 > $\mathrm{evalf}\left[15\right]\left(\mathrm{evalf}\left[20\right]\left(\mathrm{add}\left(B\right)\right)\right)$
 ${8.63950358331122}{-}{38.2988008918305}{}{I}$ (7)
 > $\mathrm{evalf}\left[15\right]\left(\mathrm{evalf}\left[20\right]\left(\mathrm{PairwiseSummation}\left(B\right)\right)\right)$
 ${8.63950358331123}{-}{38.2988008918305}{}{I}$ (8)

We see that the result (8) by PairwiseSummation only changed the last couple of digits of (6) while the result (7) by add changed various trailing digits of (5) and actually came closer to (6) by PairwiseSummation. Since these last two results (7) and (8) are assured to have less round-off error that (5) and (6), we see that (6) using PairwiseSummation has less less round-off error (2 to 4 more correct digits) than (5).

In conclusion from this experiment, depending on the random sample of complex numbers, for example for Digits = 15 we can expect say from two to four more correct digits when adding using pairwise summation than when adding the same numbers one at a time. In practice, even adding a small amount of numbers with Digits = 10, we can expect one to two more correct digits when performing the addition using the pairwise technique.

References

 [1] Wikipedia, "Pairwise summation". http://en.wikipedia.org/wiki/Pairwise_summation

Compatibility

 • The MathematicalFunctions[Evalf][PairwiseSummation] command was introduced in Maple 2017.