zbMATH — the first resource for mathematics

Fast Fourier transforms for nonequispaced data. (English) Zbl 0791.65108
The paper presents interesting fast algorithms generalizing the fast Fourier transform to the case of noninteger frequencies and nonequidistant nodes on the interval \([-\pi,\pi]\). The described algorithms are approximate ones, i.e. the calculations are performed with a fixed relative accuracy \(\varepsilon \geq 0\). They are based on a combination of results of the approximation by trigonometric polynomials and fast Fourier transform techniques.
The algorithms require \(O(N \log N+N \log(1/ \varepsilon))\) arithmetic operations. Several numerical examples illustrate the efficiency of the approach.

65T50 Numerical methods for discrete and fast Fourier transforms
65T40 Numerical methods for trigonometric approximation and interpolation
65Y20 Complexity and performance of numerical algorithms
42A10 Trigonometric approximation
Full Text: DOI