BIT, 30 (1990), pp. 268-288.
Ömer Egecioglu, Stratis Gallopoulos, and Cetin K. Koc
A Parallel Method for Fast and Practical High-Order Newton Interpolation
Abstract.
We present fast and practical parallel algorithms for the computation
and evaluation of interpolating polynomials. The algorithms
make use of fast parallel prefix techniques for the calculation of
divided differences in the Newton representation of the interpolating
polynomial. For N+1 given input pairs the proposed interpolation
algorithm requires only $2\lceil \log (N+1) \rceil +2$ parallel
arithmetic steps and circuit size $O(N^2)$, reducing the best known circuit
size for parallel interpolation by a factor of $\log N$. The algorithm
for the computation of the divided differences is shown to be numerically
stable and does not require equidistant points, precomputation, or the
fast Fourier transform. We report on numerical experiments comparing this
with other serial and parallel algorithms. The experiments indicate that
the method can be very useful for very high-order interpolation, which
is made possible for special sets of interpolation nodes.
omer@cs.ucsb.edu