Fast algorithms for discrete polynomial transforms on arbitrary grids

Consider the Vandermonde-like matrix P := (P-k(x(M,l)))(l,k=0)(M,N), where the polynomials P-k satisfy a three-term recurrence relation and x(M,l) is an element of [-1,1] are arbitrary nodes. If P-k are the Chebyshev polynomials T-k, then P coincides with A := (T-k (x(M,l)))(l=0),(k=0). This paper presents a fast algorithm for the computation of the matrix-vector product Pa in O(N log(2) N) arithmetical operations. The algorithm divides into a fast transform which replaces Pa with Aa and a fast cosine transform on arbitrary nodes (NDCT). Since the first part of the algorithm was considered, in [Math. Comp. 67 (1998) 1577], we focus on approximative algorithms for the NDCT. Our considerations are completed by numerical tests. (C) 2003 Elsevier Science Inc. All rights reserved.