A fast algorithm for scalar Nevanlinna-Pick interpolation

DOI10.1007/BF01388683MaRDI QIDQ1326428zbMATH OpenFDO

Authors Çetin Kaya Koç, Guanrong Chen

Publication date 6 June 1994

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/133699

zbMATH Keywords

fast algorithmFenyves arrayinterpolatory rational functionNevanlinna-Pick interpolation

Mathematics Subject Classification ID

Approximation in the complex plane (30E10) Numerical interpolation (65D05) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05)

Review text

We derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Given \(n\) distinct points \(z_ i\) in the unit disk \(| z |<1\) and \(n\) complex numbers \(w_ i\) satisfying the Pick condition for \(1 \leq i \leq n\), the new Nevanlinna-Pick interpolation algorithm requires only \(O(n)\) arithmetic operations to evaluate the interpolatory rational function at a particular value of \(z\), in contrast to the classical algorithm which requires \(O(n^ 2)\) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring only \(O(\log n)\) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine with \(n\) processors. We must remark that the rational function \(f(z)\) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.

Recommendations

• A fast algorithm for Nevanlinna-Pick interpolation
• Publication:4486596
• Parallel algorithms for nevanlinna-pick interpolation:the scalar case^∗
• scientific article; zbMATH DE number 7254046
• A new algorithm for meromorphic Nevanlinna-Pick interpolation
• A fast algorithm for optimal linear interpolation
• scientific article; zbMATH DE number 1492796
• Computing matrix-valued Nevanlinna-Pick interpolation
• scientific article; zbMATH DE number 15038
• Fast algorithms for multivariate interpolation and evaluation at special points

Cites work

• A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
• Depth-size trade-offs for parallel prefix computation
• Efficient parallel algorithms for linear recurrence computation
• scientific article; zbMATH DE number 3940034 (Why is no real title available?)
• scientific article; zbMATH DE number 3954267 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• On Parallel Searching
• Parallel algorithms for nevanlinna-pick interpolation:the scalar case^∗
• Parallel Prefix Computation
• Parallelism in random access machines
• Signal processing and systems theory. Selected topics

Cited in

(12)

• On hyperbolic divided differences and the Nevanlinna-Pick problem
• Computing matrix-valued Nevanlinna-Pick interpolation
• Interpolation on arbitrary regions in the complex plane
• A new algorithm for meromorphic Nevanlinna-Pick interpolation
• Numerical determination of hitting time distributions from their Laplace transforms: simple cases
• Parallel algorithms for nevanlinna-pick interpolation:the scalar case^∗
• scientific article; zbMATH DE number 4157169 (Why is no real title available?)
• A fast algorithm for Nevanlinna-Pick interpolation
• scientific article; zbMATH DE number 1466438 (Why is no real title available?)
• Nevanlinna Pick interpolation of attractors
• Nevanlinna-Pick interpolation by rational functions with a single pole inside the unit disk
• A vector-efficient and memory-saving interpolation algorithm for PIC codes on a Cray X-MP

This page was built for publication: A fast algorithm for scalar Nevanlinna-Pick interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1326428)