International Journal of Computer Mathematics, 32 (1990), pp. 217-231.
Ömer Egecioglu and Cetin K. Koc
Parallel Rational Interpolation
Abstract.
A fast parallel algorithm for rational interpolation based on orthogonal
polynomials, which is suitable for both shared-memory and message-passing
multiprocessor systems is proposed. In the shared-memory case with
N+1 identical processors, the algorithm requires $O(N\log N)$ parallel
arithmetic steps to construct all rational interpolants at once, where
N+1 is the number of data points. Extensions to message-passing
multiprocessor systems such as the hypercube are also discussed.
The hypercube version of the algorithm requires $O(N\log N)$ parallel
arithmetic steps and at most $O(N\log N)$ inter-processor communication
overhead. Thus in effect, the algorithm constructs each rational
interpolant using $O(\log N)$ parallel arithmetic and $O(\log N)$
communication steps.
omer@cs.ucsb.edu