The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices

In this paper we compare the numerical properties of the well-known fast O(n(2)) Traub and Bjorck-Pereyra algorithms, which both use the special structure of a Vandermonde matrix to rapidly compute the entries of its inverse. The results of numerical experiments suggest that the Parker variant of what we shall call the Parker-Traub algorithm allows one not only fast O(n(2)) inversion of a Vandermonde matrix, but it also gives more accuracy. We also show that the Parker-Traub algorithm is connected to the well-known concept of displacement rank, introduced by Kailath, Kung, and Morf about two decades ago, and therefore this algorithm can be generalized to invert the more general class of Vandermonde-like matrices, naturally suggested by the idea of displacement. (C) 1997 Academic Press.