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 systolic/wavefront arrays. The classical algorithm for the Nevanlinna-Pick interpolation requires O(n2) arithmetic operations to compute the entries of the Fenyves array and O(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 O(n) arithmetic operations and O(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 O(n) processors in evaluating the interpolatory rational function using O(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. © 1991, Taylor & Francis Group, LLC. All rights reserved.