Parallel Algorithms For Nevanlinna-Pick Interpolation : The Scalar Case

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations



Original languageEnglish
Pages (from-to)99-115
Journal / PublicationInternational Journal of Computer Mathematics
Issue number1-2
Publication statusPublished - Jan 1991
Externally publishedYes


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.

Research Area(s)

  • computational complexity, Fenyves array, Nevanlinna-Pick interpolation, Optimal control, parallelism, systolic computation