Parallel Hermite interpolation: An algebraic approach

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²) processors is presented. The algorithm relies on a novel closed formula that yields the expansion of the generalized divided differences in terms of the given function and derivative values. We show that each one of the coefficients in this expansion 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