# Fast (approximate) evaluation of Chebyshev polynomial

Is there a preferred way how to implement a fast (approximate) evaluation of the Chebyshev interpolation polynomial on uniform grid (given the function values at the Chebyshev nodes)? My problem is that the interpolation becomes slow when the degree of the interpolating polynomial increases.

The following ideas came to my mind:

• Try to adapt non-uniform FFT (NFFT) techniques
• Use FFT to compute the derivates at the Chebyshev nodes, potentially after first going to a finer (Chebyshev) grid. Then use a piecewise cubic interpolation for (approximative) evaluation.
• Use some formula that only uses function values (and potentially derivatives) at "nearby" Chebyshev nodes (this is related a specific NFFT technique).
• Have a look at chebfun! It is a whole library that bases on function representations by means of Chebyshev polynomials. It is open source, highly optimized, and well maintained and I guess that if there exists a preferred way for the pointwise evaluation of a polynomial, then you will find it there. – Jan Oct 15 '17 at 1:26

This is actually an exact evaluation of the Chebyshev interpolant. If you're evaluating a polynomial of degree $n$ at $m$ nodes, the cost is in $\mathcal O(nm)$.
• @ThomasKlimpel: How are you computing the weights? If you're using Chebyshev nodes on $[-1,1]$, they're just $\pm 1$, or $\pm 1/2$ at the edges. If speed is really of the essence, I've added the Clenshaw algorith to my reply. In my experience, it's about four times faster in compiled code. – Pedro Oct 4 '12 at 9:34