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