In many instances the discrete Fourier transform (DFT) is desired for a data set that occurs on an irregular grid. Commonly the data are interpolated to a regular grid, and a fast Fourier transform (FFT) is then applied. A drawback to this approach is that typically the data have unknown smoothness properties, so that the error in the interpolation is unknown. An alternative method is presented, based upon multilevel integration techniques introduced by A. Brandt. In this approach, the kernel, e(-iwt), is interpolated to the irregular grid, rather than interpolating the data to the regular grid. This may be accomplished by pre-multiplying the data by the adjoint of the interpolation matrix (a process dubbed anterpolation), producing a new regular-grid function, and then applying a standard FFT to the new function. Since the kernel is C infinity the operation may be carried out to any preselected accuracy. A simple optimization problem can be solved to select the problem parameters in an efficient way. If the requirements of accuracy are not strict, or if a small bandwidth is of interest, the method can be used in place of an FFT even when the data are regularly spaced.

Institute for Mathematics and Its Applications (IFAIA)

http://archive.org/details/dftsonirregularg00hens