# Parallel Kahan summation

• williamshipman
In summary, the parallel reduction code you are working on produces several sum/compensation pairs that need to be added together. This can be handled by returning both the "sum" and "c" values from each parallel branch, and then using Kahan summation to add them all together. Double-single precision math may be unnecessary for some operations, but it is a good option for others.

#### williamshipman

Hi PF,

I am working on a parallel reduction code to sum up approximately 1 million 32-bit floating point numbers. The serial part running on each processor uses Kahan summation, no problems there. My problem is that this produces several sum/compensation pairs that now need to be added together. How should this be handled, as I am unable to find helpful literature in the databases my library subscribes to? At the moment I am just adding the two compensation values and treating that as the new compensation value for one of the two numbers to be added.

Secondly, what is the correct way to handle a situation where the two sums must be weighted before summing them? At the moment if I have two Kahan summation results (sum1,compensation1) and (sum2,compensation2) I would proceed as follows: (sum,compensation) = kahan((sum1*w1,compensation1*w1), (sum2*w2,compensation2*w2)) where w1 and w2 are the weights and kahan() is the kahan summation from the paragraph above.

Any advice would be greatly appreciated.

With the notation of http://en.wikipedia.org/wiki/Kahan_summation_algorithm , I guess the best method would be to return both "sum" and "c" from each parallel branch, and then in the final step add all the sum's and c's using Kahan summation.

The second question depends whether you are happy with the floating point approximation ##w(a+b) = (wa) + (wb)##. In general that is not true (for example you can easily invent examples where one result gives an overflow or underflow, but the other does not) but whether it matters to you depends on much more information than is in your OP.

• 1 person
Hi AlephZero,

If I understand you properly, you're suggesting that I do the following for question 1:
1. Kahan summation of sum1, sum2 up to sumN, giving an ##s## and ##c## value.
2. Kahan summation of compensation1 up to compensationN, giving an ##s## and ##c## value.
At the end of this, I would come out with a sum of all the sums and its compensation term, a sum of all the previous compensation values, and its compensation term. Did I follow that correctly?

Regarding question 2, I think you misunderstood me. I am trying to calculate ##w_1 a + w_2 b##, i.e. two different weights and ##a## and ##b## are both results from previous Kahan summations.

To answer my original question, the correct way to handle my problem seems to be to use what is known as double-single precision math. See http://crd-legacy.lbl.gov/~dhbailey/mpdist/ for Fortran code for a double-single and double-double precision libraries. Unfortunately, once one gets to multiplication and division operations, which I need a lot of, the amount of operations becomes quite large, making it pointless for me to pursue double-single precision in place of plain double precision.

## What is Parallel Kahan summation?

Parallel Kahan summation is a method used for the summation of a large number of floating point numbers in parallel. It is based on the Kahan summation algorithm, which is known for its accuracy in avoiding floating point errors.

## How does Parallel Kahan summation work?

Parallel Kahan summation works by dividing the array of numbers into smaller sub-arrays, which are then summed up in parallel. These sub-arrays are then summed again to get the final result. This approach reduces the number of floating point operations and improves the accuracy of the sum.

## What are the advantages of using Parallel Kahan summation?

Parallel Kahan summation has several advantages, including improved accuracy in the final result, reduced number of floating point operations, and the ability to handle large arrays of numbers efficiently. It also allows for easier parallelization, which can improve performance on multi-core processors.

## Are there any limitations of Parallel Kahan summation?

One limitation of Parallel Kahan summation is that it may not be suitable for all types of parallel architectures. It also requires additional memory for storing the sub-arrays, which may be a concern for systems with limited memory. Additionally, it may not provide significant improvements in performance for small arrays of numbers.

## What are some real-world applications of Parallel Kahan summation?

Parallel Kahan summation is commonly used in scientific computing, particularly in applications that involve large arrays of floating point numbers, such as data analysis, simulations, and machine learning. It is also used in high-performance computing and parallel programming to improve the efficiency and accuracy of summations in parallel algorithms.