×

The regular Fourier matrices and nonuniform fast Fourier transforms. (English) Zbl 0941.65152

Let \(m\in\mathbb{N}\) and let \(q\), \(N\) be even. Set \(w= \exp(2\pi i/mN)\). In this interesting paper, the authors present a fast Fourier transform for unequally spaced data and equidistant frequencies \[ f_j= \sum^{N-1}_{k= 0}\alpha_k w^{jmc_k}\qquad (j=-N/2,\dots, N/2-1) \] with \(c_k\in [-N/2, N/2]\) and \(\alpha_k\in\mathbb{C}\). Note that usually \(m=2\), \(N\ll 1\), and \(q\approx- \log\varepsilon\), where \(\varepsilon\) is the precision. This method is based on a least-squares solution of a linear system related to the so-called regular Fourier matrix. It simplifies and improves the nonuniform fast Fourier transform of A. Dutt and V. Rokhlin [SIAM J. Sci. Comput. 14, No. 6, 1368-1393 (1993; Zbl 0791.65108)]. The total complexity of this algorithm is \(O(Nq^2- mN\log N)\).
Reviewer: M.Tasche (Rostock)

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65Y20 Complexity and performance of numerical algorithms

Citations:

Zbl 0791.65108
Full Text: DOI