Fast algorithms for discrete polynomial transforms

Consider the Vandermonde-like matrix ${\mathbf{P}}:=(P_k(\cos\frac{j\pi}{N}))_{j,k=0}^N$, where the polynomials $P_k$ satisfy a three-term recurrence relation. If $P_k$ are the Chebyshev polynomials $T_k$, then ${\mathbf{P}}$ coincides with ${\mathbf{C}}_{N+1}:= (\cos\frac{jk\pi}{N})_{j,k=0}^N$. This paper presents a new fast algorithm for the computation of the matrix-vector product ${\mathbf{Pa}}$ in $O(N \log^2N)$ arithmetical operations. The algorithm divides into a fast transform which replaces ${\mathbf{Pa}}$ with ${\mathbf{C}}_{N+1} {\mathbf{\tilde a}}$ and a subsequent fast cosine transform. The first and central part of the algorithm is realized by a straightforward cascade summation based on properties of associated polynomials and by fast polynomial multiplications. Numerical tests demonstrate that our fast polynomial transform realizes ${\mathbf{Pa}}$ with almost the same precision as the Clenshaw algorithm, but is much faster for $N\ge 128$.