Fast Fourier transforms (FFTs) belong to the '10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century'. The classic algorithm computes the discrete Fourier transform \[ f_j= \sum_{k=-\frac{N}{2}}^{\frac{N}{2}-1} \hat{f}_{k} {\rm e}^{2\pi{\rm i}\frac{kj}{N}} \] for \(j=-\frac{N}{2},\dots,\frac{N}{2}-1\) and given complex coefficients \(\hat{f}_{k}\in\mathbb{C}\). Using a divide and conquer approach, the number of floating point operations is reduced from \({\mathcal O}(N^2)\) for a straightforward computation to only \({\mathcal O}(N\log N)\). In conjunction with publicly available efficient implementations the fast Fourier transform has become of great importance in scientific computing.

However, two shortcomings of traditional schemes are the need for equispaced sampling and the restriction to the system of complex exponential functions. The NFFT (nonequispaced fast Fourier transform or nonuniform fast Fourier transform, NUFFT) is a C subroutine library for computing the nonequispaced discrete Fourier transform (NDFT) and its generalisations in one or more dimensions, of arbitrary input size, and of complex data.

More precisely,we collect the possible frequencies \(\mathbf{k}\in\mathbb{Z}^d\) in the multi-index set \[ I_{\mathbf{N}} := \left\{ \mathbf{k}=\left(k_t\right)_{t=0,\dots,d-1} \in \mathbb{Z}^d: - \frac{N_t}{2} \le k_t \lt \frac{N_t}{2} ,\;t=0,\dots,d-1\right\}, \] where \(\mathbf{N}=\left(N_t\right)_{t=0,\dots,d-1}\) is the multibandlimit, i.e., \(N_t\in 2\mathbb{N}\). For a finite number of given Fourier coefficients \(\hat f_{\mathbf{k}} \in \mathbb{C}\), \(\mathbf{k}\in I_{\mathbf{N}}\), we consider the fast evaluation of the trigonometric polynomial \[ f\left(\mathbf{x}\right) := \sum_{ \mathbf{k}\in I_{ N}} \hat{f}_{\mathbf{ k}} {\rm e}^{-2\pi{\rm i}\mathbf{k}\mathbf{ x}} \] at given nonequispaced nodes \(\mathbf{x}_j \in \mathbb{T}^d\), \(j=0,\ldots, M-1\), from the \( d\)-dimensional torus as well as the adjoint problem, the fast evaluation of sums of the form \[ \hat h_{\mathbf{k}} := \sum_{j=0}^{M-1} {f}_{j} {\rm e}^{2\pi{\rm i}\mathbf{k}\mathbf{ x}_j}. \] In general, the adjoint NDFT is not the inverse transform of the NDFT.

The generalisations of the NFFT include

• NNFFT - nonequispaced in time and frequency fast Fourier transform
• NFCT/NFST - nonequispaced fast (co)sine transform
• NSFFT - nonequispaced sparse fast Fourier transform (hyperbolic cross)
• FPT - fast polynomial transform
• NFSFT - nonequispaced fast spherical Fourier transform
• NFSOFT - nonequispaced fast Fourier transform on the rotation group SO(3)

Furthermore, we consider the inversion of the above transforms by iterative methods.

The NFFT is a C subroutine library for computing the nonequispaced discrete Fourier transform (NDFT) in one or more dimensions, of arbitrary input size, and of complex data. New: A Matlab interface is part of the NFFT3. We believe that our library, which is free software, and based on (FFTW 3.x) should become the NFFT library of choice for most applications.

The NFFT package has been developed at the Mathematical Institute of the University of Lübeck, at the Mathematical Institute of the University Osnabrück and at the Faculty of Mathematics of the Chemnitz University of Technology by Jens Keiner, Stefan Kunis and Daniel Potts. Further contributions, in particular applications, are due to Dr. Markus Fenn, Steffen Klatt, Tobias Knopp and Antje Vollrath. The support for OpenMP was developed by Toni Volkmer. Many contributions to the release 3.3.* and later are done by Toni Volkmer and Michael Quellmalz, see developers.

If you have any comments, questions, or suggestions regarding NFFT, don't hesitate to email at potts@mathematik.tu-chemnitz.de.

	counter