On the parallel evaluation of a sparse polynomial at a point

A new version of the Ruffini–Horner rule is presented for the evaluation of a polynomial of degree n at a point. In the PRAM model of parallel computation the new algorithm requires log n parallel steps with n/2+1 processors and the total number of arithmetic operations is n+⌈log₂(n+1)⌉ -1 multiplications and n additions. If the polynomial is sparse, i.e., the number of nonzero coefficients is k≪ n, then the total number of operations is at most k(⌈log n⌉- ⌊log k⌋)+2k+⌈log n⌉. Moreover, similarly to the customary Ruffini–Horner rule, the algorithm is backward numerically stable. In other words, the value provided by applying the algorithm in floating point arithmetic with machine precision μ coincides with the value taken on at the same point by a slightly perturbed polynomial. This revised version was published online in June 2006 with corrections to the Cover Date.