𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A summation algorithm with error correction for parallel computers

✍ Scribed by Kazufumi Ozawa; Masatoshi Miyazaki

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
413 KB
Volume
24
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper proposes an algorithm to accurately compute the sum of floating‐point numbers on parallel computers. This algorithm is an extension of the well‐known recursive doubling technique which computes the sum of n floating‐point number in log~2~n parallel steps. The time complexity of the present algorithm also is O(log n), and the space complexity is O(n). This algorithm enables a highly accurate result to be obtained with guarantee. The theoretical analysis and the numerical experiments on a parallel computer show that this algorithm is as accurate as Kahan's, which is the fastest and an accurate serial algorithm for the summation of the numbers, and also that the present algorithm is faster than Kahan's provided that two or more processors are available.

πŸ“œ SIMILAR VOLUMES

Parallel implementation of a ray tracing
Parallel implementation of a ray tracing algorithm for distributed memory parallel computers
✍ Lee, Tong-Yee; Raghavendra, C. S.; Nicholas, John B. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 145 KB πŸ‘ 3 views

Ray tracing is a well known technique to generate life-like images. Unfortunately, ray tracing complex scenes can require large amounts of CPU time and memory storage. Distributed memory parallel computers with large memory capacities and high processing speeds are ideal candidates to perform ray tr

Parallel Computation and Indefinite Summ
Parallel Computation and Indefinite Summation: a β€–MAPLEβ€– Application for the Rational Case
✍ Roberto Pirastu; Kurt Siegl πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 439 KB

The problem of computing a closed form for sums of special functions arises in many parts of mathematical and computer science, especially in combinatorics and complexity analysis. Here we discuss two algorithms for indefinite summation of rational functions, due to Abramov (1975) and Paule (1993).