Fast inversion of Vandermonde-like matrices involving orthogonal polynomials (Q1314634): Difference between revisions

The Vandermonde-like matrices considered in this paper are of the same structure as a classical Vandermonde matrix except that the values of monomials are replaced by those of orthogonal polynomials. A fast algorithm, inspired by work of \textit{J. F. Traub} [SIAM Rev. 8, 277-301 (1966; Zbl 0249.65018)], is introduced and tested. The cost of inverting the matrix is quadratic in the order of the matrix rather than cubic as for standard Gaussian elimination. It is shown that the algorithm gives more accurate results than Gaussian elimination. It is also demonstrated that the accuracy depends on the distribution of the points and that a Leja ordering corresponds to a strategy that improves the performance. The paper is written very clearly and contains a number of references to the literature.