A fast algorithm for scalar Nevanlinna-Pick interpolation

In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Given n distinct points z_i in the unit disk |z|i satisfying the Pick condition for 1≦i≦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²) 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. © 1993 Springer-Verlag.