Computing, 42 (1989), pp. 291-307.
Ömer Egecioglu, Stratis Gallopoulos, and Cetin K. Koc
Parallel Hermite Interpolation: An Algebraic Approach
Abstract.
Given N+1 distinct points and arbitrary order derivative information
at these points, a parallel algorithm to compute the coefficients of
the corresponding Hermite interpolating polynomial in $O(\log N)$
parallel arithmetic operations using $O(N^2)$ processors is presented.
The algorithm relies on a novel closed formula that yields the coefficients
when the generalized divided differences are expressed linearly in terms of
the given function and derivative values. We show that each one of these
coefficients and the required linear combinations can be evaluated
efficiently. The particular cases where up to first and second order
derivative information is available are treated in detail. The proof of
the general case, where arbitrarily high order derivative information is
available, involves algebraic arguments that make use of the theory of
symmetric functions.
omer@cs.ucsb.edu