The Regular Fourier Matrices and Nonuniform Fast Fourier Transforms

From MaRDI portal





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 \textit{A. Dutt} and \textit{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)\).











This page was built for publication: The Regular Fourier Matrices and Nonuniform Fast Fourier Transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4702381)