Journal of Complexity, 5 (1989), pp. 417-437.
Ömer Egecioglu, Stratis Gallopoulos, and Cetin K. Koc
Fast Computation of Divided Differences and Parallel Hermite
Interpolation
Abstract.
We present parallel algorithms for fast polynomial interpolation.
These algorithms can be used for constructing and evaluating polynomials
interpolating the function values and its derivatives of arbitrary order
(Hermite interpolation). For interpolation, the parallel arithmetic
complexity is $O(\log^{2}M + \log N)$ for large M and N,
where M-1 is the order of the highest derivative information and N
is the number of distinct points used. Unlike alternate approaches
which use the Lagrange representation, the algorithms described in this paper
are based on the fast parallel evaluation of a closed formula
for the generalized divided differences. Applications to the solution
of dual Vandermonde and confluent Vandermonde systems are described.
This work extends previous results in polynomial interpolation and
improves the parallel time complexity of existing algorithms.
omer@cs.ucsb.edu