Abstract
Let {q} =0n−1 j be a family of polynomials that satisfy a three-term recurrence relation and let {t k } =1n k be a set of distinct nodes. Define the Vandermonde-like matrixW n =[w jk ] =1n k,j ,w jk =q j−1(t k ). We describe a fast algorithm for computing the elements of the inverse ofW n inO(n 2) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n 3) arithmetic operations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Almacany, C. B. Dunham and J. Williams,Discrete Chebyshev approximation by interpolating rationals, IMA J. Numer. Anal., 4 (1984), pp. 467–477.
E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen,LAPACK Users' Guide, SIAM, Philadelphia, 1992.
Å. Björck and V. Pereyra,Solution of Vandermonde systems of equations, Math. Comp., 24 (1970), pp. 893–903.
J. R. Bunch,The weak and strong stability of algorithms in numerical linear algebra, Linear Algebra Appl., 88/89 (1988), p. 49–66.
D. Calvetti and L. Reichel,A Chebyshev-Vandermonde solver, Linear Algebra Appl., 172 (1992), pp. 219–229.
J. Chun and T. Kailath,Displacement structure for Hankel, Vandermonde and related (derived) matrices, Linear Algebra Appl., 151 (1991), pp. 199–227.
J. J. Donngarra, J. R. Bunch, C. B. Moler and G. W. Stewart,LINPACK Users' Guide, SIAM Philadelphia, 1979.
J. Du Croz and N. J. Higham,Stability of methods for matrix inversion, IMA J. Numer. Anal., 12 (1992), pp. 1–19.
W. Gautschi,The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl., 52/53 (1983), pp. 293–300.
W. Gautschi,How (un)stable are Vandermonde systems?, in Asymptotic and Computational Analysis, ed. R. Wong, Lecture Notes in Pure and Applied Mathematics, v. 124, Dekker, New York, 1990, pp. 193–210.
W. Gautschi and G. Inglese,Lower bounds for the condition number of Vandermonde matrices, Numer. Math., 52 (1988), pp. 241–250.
I. Gohberg, T. Kailath and I. Koltracht,Efficient solution of linear systems of equations with recursive structure, Linear Algebra Appl., 80 (1986) pp. 81–113.
G. Heinig and K. Rost,Algebraic Methods for Toeplitz-like Matrices and Operators, Birkhäuser, Basel, 1984.
N. J. Higham,Error analysis of the Björck-Pereyra algorithms for solving Vandermonde system, Numer. Math., 50 (1987), pp. 613–632.
N. J. Higham,Fast solution of Vandermonde-like systems involving orthogonal polynomials, IMA J. Numer. Anal., 8 (1988), pp. 473–486.
N. J. Higham,Stability analysis of algorithms for solving confluent Vandermonde-like systems, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 23–41.
F. Leja, Sur certaines suites liées aux ensemble plans et leur application à la representation conforme, Ann. Polon. Math., 4 (1957), pp. 8–13.
N. Macon and A. Spitzbart,Inverses of Vandermonde matrices, Amer. Math. Monthly, 65 (1958), pp. 95–100.
L. Reichel,Newton interpolation at Leja points, BIT, 30 (1990), pp. 332–346.
L. Reichel and G. Opfer,Chebyshev-Vandermonde systems, Math. Comp., 57 (1991), pp. 703–721.
W. P. Tang and G. H. Golub,The block decomposition of a Vandermonde matrix and its applications, BIT 21 (1981), pp. 505–517.
J. F. Traub,Associated polynomials and uniform methods for the solution of linear problems, SIAM Review, 8 (1966), pp. 277–301.
L. Verde-Star,Inverses of generalized Vandermonde matrices, J. Math. Anal. Appl., 131 (1988), pp. 341–353.
Author information
Authors and Affiliations
Additional information
Dedicated to Gene H. Golub on his 60th birthday
Research supported by NSF grant DMS-9002884.
Rights and permissions
About this article
Cite this article
Calvetti, D., Reichel, L. Fast inversion of vandermonde-like matrices involving orthogonal polynomials. BIT 33, 473–484 (1993). https://doi.org/10.1007/BF01990529
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01990529