Parallel algorithms for nevanlinna-pick interpolation:the scalar case^∗

We study the parallel computational complexity of the Nevanlinna-Pick interpolation and introduce several parallel algorithms suitable for implementation on shared-memory multiprocessors and systo-lic/wavefront arrays. The classical algorithm for the Nevanlinna-Pick interpolation requires 0(n 2) arithmetic operations to compute the entries of the Fenyves array and 0(n) arithmetic operations to evaluate the interpolatory rational function at a given point. We propose an algorithm for parallel computation of the Fenyves array using 0(h) arithmetic operations and 0(n) processors. Furthermore, we propose a modification of the classical algorithm for fast and parallel implementation of the evaluation step. The resulting parallel algorithm requires 0(n) processors in evaluating the interpolatory rational function using 0(log n) arithmetic operations. Finally, we introduce time-optimal and spacetime-optimal systolic algorithms for computing the entries of the Fenyves array and evaluating the interpolatory rational function. Keywords: Optimal controlNevanlinna-Pick interpolationFenyves arraycomputational complexityparallelismsystolic computationC.R. Categories: F.2G.1.0G.1.1G.1.2 ∗Report No. 215, Center for Approximation Theory, Texas A&M University, May 1990. This work is partially supported by the US Army Research Office Grant No. DAAL03-91-G-0106 and the RIG program at the University of Houston. ∗Report No. 215, Center for Approximation Theory, Texas A&M University, May 1990. This work is partially supported by the US Army Research Office Grant No. DAAL03-91-G-0106 and the RIG program at the University of Houston. Notes ∗Report No. 215, Center for Approximation Theory, Texas A&M University, May 1990. This work is partially supported by the US Army Research Office Grant No. DAAL03-91-G-0106 and the RIG program at the University of Houston.