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

The authors compare the fast generalized Parker-Traub and Björck-Pereyra algorithms for calculating the inverse of Vandermonde matrices. They find that although the Traub algorithm is numerically unstable, the earlier algorithm of Parker, which is almost identical, is not only faster than the Björck-Pereyra algorithm, but it is also more accurate, as shown in several examples. They also show that the Parker-Traub algorithm is connected to Kailath, Kung and Morf's concept of displacement rank, which then allows them to extend the algorithm to Vandermonde-like matrices, which are naturally suggested by the idea of displacement. The authors quote \textit{N. J. Higham's} paper [Numer. Math. 50, 613-632 (1987; Zbl 0595.65029)], in which the accuracy of the Björck-Pereyra algorithm is proven for a restricted set of Vandermonde matrices, while for the unmodified Traub algorithm a comment is offered about potential catastrophic cancellation. Then they observe that the Parker algorithm could suffer from the same ailment, but the numerical results do not support this possibility. It would be interesting to provide a Higham type result for the Parker algorithm which would indicate if there are any limitations to its apparently good behavior. (We can hardly forget that the Björck-Pereyra algorithm was happily used for 20 years before Higham's deep analysis.) Incidentally, both Higham and the present authors have given the reviewer and Ake Björck unprecedented propaganda on what, at least from this reviewer's point of view, is not a major piece of work. However, if we want to respect the historical perspective, it would be more appropriate to call this algorithm Ballester-Björck-Pereyra algorithm [c.f. \textit{C. Ballester} and \textit{V. Pereyra}, On the construction of discrete approximations to linear differential expressions, Math. Comput. 21, 297-302 (1967; Zbl 0168.14103)].