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

Abstract

A Chebyshev or Fourier series may be evaluated on the standard collocation grid by the fast Fourier transform (FFT). Unfortunately, the FFT does not apply when one needs to sum a spectral series at N points which are spaced irregularly. The cost becomes O(N2) operations instead of the FFTs O(N log N). This sort of "off-grid" interpolation is needed by codes which dynamically readjust the grid every few time steps to resolve a shock wave or other narrow features. It is even more crucial to semi-Lagrangian spectral algorithms for solving convection-diffusion and Navier-Stokes problems because off-grid interpolation must be performed several times per time step. In this work, we describe an alternative algorithm. The first step is to pad the set of spectral coefficients {an} with zeros and then take an FFT of length 3N to interpolate the Chebyshev series to a very fine grid. The second step is to apply either the Mth order Euler sum acceleration or (2M + 1)-point Lagrangian interpolation to approximate the sum of the series on the irregular grid. We show that both methods yield full precision with M N, allowing an order of magnitude reduction in cost with no loss of accuracy.