TY - JOUR
T1 - Parallel Algorithms For Nevanlinna-Pick Interpolation
T2 - The Scalar Case
AU - Koç, Çetin K.
AU - CHEN, Guanrong
PY - 1991/1
Y1 - 1991/1
N2 - 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.
AB - 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.
KW - computational complexity
KW - Fenyves array
KW - Nevanlinna-Pick interpolation
KW - Optimal control
KW - parallelism
KW - systolic computation
UR - http://www.scopus.com/inward/record.url?scp=84916492514&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84916492514&origin=recordpage
U2 - 10.1080/00207169108804005
DO - 10.1080/00207169108804005
M3 - 21_Publication in refereed journal
VL - 40
SP - 99
EP - 115
JO - International Journal of Computer Mathematics
JF - International Journal of Computer Mathematics
SN - 0020-7160
IS - 1-2
ER -