Fast inversion of Chebyshev-Vandermonde matrices (Q1326471)

Two fast algorithms for numerical inversion of Chebyshev-Vandermonde matrices \(V_ P(t)=(P_ j (t_ i))^{n-1}_{i,j=0}\) are proposed. Here \(t_ i\) are complex numbers and \(P_ j(\lambda)\) are Chebyshev polynomials of the first or of the second kind. Both algorithms compute all \(n^ 2\) entries of the inverse matrix in \(7n^ 2\) arithmetic operations. These algorithms are based on new explicit formulas for inverse matrix involving Bézoutians. The paper contains also results of numerical experiments, which show that accuracy depends on the ordering of input points, and that the proposed algorithms are not only faster, but also more stable than other algorithms available. The new algorithms are also efficient for solving linear systems with preprocessing.