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).
-

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)$.
 Currently, I do it by precomputing the weights relative to the function values at the Chebyshev nodes for a specific evaluation point, then evaluate this point for all interpolations I have to do (there are many, all with identical Chebyshev nodes and identical evaluation points), and then move on to the next evaluation point. – Thomas Klimpel Oct 4 '12 at 7:35 @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