Parallel Algorithms For Nevanlinna-Pick Interpolation : The Scalar Case
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 99-115 |
Journal / Publication | International Journal of Computer Mathematics |
Volume | 40 |
Issue number | 1-2 |
Publication status | Published - Jan 1991 |
Externally published | Yes |
Link(s)
Abstract
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
Citation Format(s)
Parallel Algorithms For Nevanlinna-Pick Interpolation: The Scalar Case. / Koç, Çetin K.; CHEN, Guanrong.
In: International Journal of Computer Mathematics, Vol. 40, No. 1-2, 01.1991, p. 99-115.
In: International Journal of Computer Mathematics, Vol. 40, No. 1-2, 01.1991, p. 99-115.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review