Parallel Hermite interpolation: An algebraic approach (Q1124261)

[This article was also presented at the First International Conference on Industrial and Applied Mathematics, Paris, June 29-July 3, 1987.] A parallel algorithm for Hermite interpolation is constructed over F, where \(n+1\) points \((x_ i,f_ i)\in F\times F\) \((i=0,1,...,n)\) and the derivatives of any order are given. The interpolation problem involves finding a polynomial \(p_ n(x)\in F[x]\) of degree n such that \(p_ n(x)=f_ i.\) The algorithm computes the coefficients (generalized divided differences) in O(log n) parallel steps using \(O(n^ 2)\) processors for a fixed number of derivatives by using parallel prefix algorithms. Detailed calculations are described for the cases \(f(x_ i)\) and \(f'(x_ i)\) given for \(0\leq i\leq n\) and \(f(x_ i)\), \(f'(x_ i)\) and \(f''(x_ i)\) given for \(0\leq i\leq n\).