Affordable Access

Publisher Website

The Fast Generalized Parker–Traub Algorithm for Inversion of Vandermonde and Related Matrices

Authors
Journal
Journal of Complexity
0885-064X
Publisher
Elsevier
Publication Date
Volume
13
Issue
2
Identifiers
DOI: 10.1006/jcom.1997.0442
Disciplines
  • Computer Science

Abstract

Abstract In this paper we compare the numerical properties of the well-known fast O( n 2) Traub and Björck–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-likematrices, naturally suggested by the idea of displacement.

There are no comments yet on this publication. Be the first to share your thoughts.