Abstract: dvi (2K), pdf (73K).
Paper: pdf (1297K).
It is shown that an arithmetic expression with n distinct atoms, and operations of addition and multiplication over a ring can be evaluated in time 4 log2n + 2(n-1)/p using p processors. If division is allowed, the time is 4 log2n + 10(n-1)/p, as shown in . These results are within small constant factors of the best possible.
It is also shown that the algorithm for parallel evaluation of expressions without division is numerically stable in the sense of backward error analysis.
The result on expressions including division appears in Brent . However, the error analysis does not carry over to expressions with division.
Go to next publication
Return to Richard Brent's index page