zbMATH — the first resource for mathematics

Fast approximate Fourier transforms for irregularly spaced data. (English) Zbl 0917.65122
The author compares various known methods for computing Fourier transforms for irregularly spaced data including
– cubic spline interpolation through values on an equally spaced grid,
– local Chebyshev approximation (due to the author in his Ph.D. thesis, Oxford Univ., Oxford (1991)),
J. P. Boyd’s Euler sum [J. Comput. Phys. 103, No. 2, 243-257 (1992; Zbl 0768.65001)],
– approximations of complex exponentials (due to A. Dutt and V. Rokhlin, SIAM J. Sci. Comput. 14, No. 6, 1368-1393 (1993; Zbl 0791.65108)),
– Lagrange polynomial interpolation,
– local Taylor expansion (due to C. Anderson and M. D. Dahleh, ibid. 17, No. 4, 913-919 (1996; Zbl 0858.65114)),
– multipole method,
G. Beylkin’s USFFT [Appl. Comput. Harmon. Anal. 2, No. 4, 363-381 (1995; Zbl 0838.65142)].
Extensive numerical results are included.

65T50 Numerical methods for discrete and fast Fourier transforms
42A16 Fourier coefficients, Fourier series of functions with special properties, special Fourier series
Full Text: DOI