×
Gohberg, I.; Olshevsky, V.

The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices. (English) Zbl 0883.65018

J. Complexity 13, No. 2, 208-234 (1997).
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 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. C. Ballester and V. Pereyra, On the construction of discrete approximations to linear differential expressions, Math. Comput. 21, 297-302 (1967; Zbl 0168.14103)].
Reviewer: V.Pereyra (Los Altos)

Cited in 1 Review
Cited in 15 Documents

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
68Q25 Analysis of algorithms and problem complexity
65Y20 Complexity and performance of numerical algorithms

Keywords:

generalized Parker-Traub algorithm; Björck-Pereyra algorithms; inverse; Vandermonde matrices; displacement rank

Citations:

Zbl 0595.65029; Zbl 0168.14103
PDF BibTeX XML Cite
\textit{I. Gohberg} and \textit{V. Olshevsky}, J. Complexity 13, No. 2, 208--234 (1997; Zbl 0883.65018)
Full Text: DOI

References:

[1] Björck, A.; Pereyra, V., Solution of Vandermonde systems of linear equations, Math. Comput., 24, 893-903 (1970) · Zbl 0221.65054
[2] Calvetti, D.; Reichel, L., Fast inversion of Vandermonde-like matrices involving orthogonal polynomials, BIT, 33, 473-484 (1993) · Zbl 0809.65013
[3] Du Croz, J.; Higham, N., Stability of methods of matrix inversion, IMA J. Numer. Ana., 13, 1-19 (1992) · Zbl 0748.65021
[4] Forney, G., Concatenated Codes (1966), M.I.T. Press: M.I.T. Press Cambridge
[5] Gautschi, W.; Inglese, G., Lower bounds for the condition number of Vandermonde matrix, Numer. Math., 52, 241-250 (1988) · Zbl 0646.15003
[6] Gantmacher, F. R.; Krein, M. G., Oscillatory Matrices and Kernels, and Small Vibrations of Mechanical Systems (1950), Gosudarstvennoe izdatelstvo technicko-teoreticheskoi literatury: Gosudarstvennoe izdatelstvo technicko-teoreticheskoi literatury Moscow · Zbl 0041.35502
[7] Gohberg, I.; Koltracht, I., Mixed, componentwise and structured condition numbers, SIAM J. Matrix Anal. Appl., 14, 688-704 (1993) · Zbl 0780.15004
[8] Gohberg, I.; Kailath, T.; Koltracht, I.; Lancaster, P., Linear complexity parallel algorithms for linear systems of equations with recursive structure, Linear Algebra Appl., 88/89, 271-315 (1987) · Zbl 0624.65020
[9] Golub, G.; Van Loan, C., Matrix Computations (1989), Johns Hopkins Univ. Press: Johns Hopkins Univ. Press Baltimore · Zbl 0733.65016
[10] Gohberg, I.; Kailath, T.; Olshevsky, V., Fast Gaussian elimination with partial pivoting for matrices with displacement structure, Math. Comput., 64, 1557-1576 (1995) · Zbl 0848.65010
[11] Gohberg, I.; Olshevsky, V., Fast inversion of Chebyshev-Vandermonde matrices, Numer. Math., 67, 71-92 (1994) · Zbl 0791.65013
[12] Gohberg, I.; Olshevsky, V., Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl., 202, 163-192 (1994) · Zbl 0803.65053
[13] Gohberg, I.; Olshevsky, V., Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems, Integral Equations Operator Theory, 20, 44-83 (1994) · Zbl 0808.47014
[14] Gohberg, I.; Olshevsky, V., Fast algorithms with preprocessing for matrix-vector multiplication problems, Complexity, 10 (1994) · Zbl 0820.68051
[15] Higham, N., Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems, Numer. Math., 50, 613-632 (1987) · Zbl 0595.65029
[16] Higham, N., Stability analysis of algorithms for solving confluent Vandermonde-like systems, SIAM J. Matrix Anal. Appl., 11, 23-41 (1990) · Zbl 0724.65025
[17] Heinig, G.; Rost, K., Algebraic Methods for Toeplitz-like Matrices and Operators. Algebraic Methods for Toeplitz-like Matrices and Operators, Operator Theory, 13 (1984), Birkauser: Birkauser Basel · Zbl 0549.15013
[18] Kaufman, I., The inversion of the Vandermonde matrix and the transformation to the Jordan canonical form, IEEE Trans. Automatic Control, 14, 774-777 (1969)
[19] Kowalewski, G., Interpolation and genäherte Quadratur (1932), Teubner: Teubner Berlin · JFM 58.0585.02
[20] Kailath, T.; Kung, S.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 395-407 (1979) · Zbl 0433.15001
[22] Kailath, T.; Sayed, A. H., Displacement structure: Theory and applications, SIAM Rev., 37, 297-386 (1995) · Zbl 0839.65028
[23] Kailath, T.; Olshevsky, V., Displacement structure approach to polynomial Vandermonde and related matrices, Linear Algebra Appl. (1994) · Zbl 0824.15028
[24] Kailath, T.; Olshevsky, V., Displacement structure approach to Chebyshev-Vandermonde and related matrices, Integral Equations Operator Theory, 22, 65-92 (1995) · Zbl 0824.15028
[25] Lev-Ari, H.; Kailath, T., Triangular factorization of structured matrices, (Gohberg, I., I. Schur Methods in Operator Theory and Signal Processing. I. Schur Methods in Operator Theory and Signal Processing, Operator Theory: Advances and Applications, 18 (1986), Birkhauser: Birkhauser Basel) · Zbl 0761.15009
[26] Lancaster, P.; Tismenetzky, M., Theory of Matrices with Applications (1985), Academic Press: Academic Press Orlando
[27] Parker, F., Inverses of Vandermonde matrices, Amer. Math. Monthly, 71, 410-411 (1964) · Zbl 0119.25601
[28] Reichel, L., Newton interpolation at Leja points, BIT, 30, 23-41 (1990) · Zbl 0702.65012
[29] Traub, J., Associated polynomials and uniform methods for the solution of linear problems, SIAM Rev., 8, 277-301 (1966) · Zbl 0249.65018
[30] Tyrtyshnikov, E., How bad are Hankel matrices, Num. Math., 67, 261-269 (1994) · Zbl 0797.65039
[31] Wertz, H. J., On the numerical inversion of a recurrent problem: the Vandermonde matrix, IEEE Trans. Automatic Control, 10, 492 (1965)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.