A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid (Q1206566)

The problem is to evaluate efficiently the interpolatory sum \(f(x) \cong\sum f(x_ j)C_ j(x)\) at a set of \(N\) points which do not coincide with the regularly spaced interpolation points \(\{x_ j\}\). The fast Fourier transform (FFT) technique does not apply in this case and the cost of operations of direct summation becomes \(O(N^ 2)\) instead of \(O(N\log N)\) for FFT. The author proposes an alternative solution: to use the FFT of length \(3N\) to interpolate the Chebyshev series to a very fine grid and then to apply the \(M\)th order Euler sum acceleration (or (\(2M+1\))-point Lagrangian interpolation) with \(M << N\) to approximate \(f\) on the irregular grid. The cost of interpolation is significantly reduced with no loss of accuracy.