A fast algorithm for scalar Nevanlinna-Pick interpolation (Q1326428)

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.