Edit on GitHub

Welcome to NFFT3.jl

The nonequispaced fast Fourier transform or NFFT, see [Keiner, Kunis, Potts, 2006] and [Plonka, Potts, Steidl, Tasche, 2018], overcomes one of the main shortcomings of the FFT - the need for an equispaced sampling grid. Considering a $d$-dimensional trigonometric polynomial

\[ f(\pmb{x}) \coloneqq \sum_{ \pmb{k} \in I_{\pmb{N}}^d} \hat{f}_{\pmb{k}} \, \mathrm{e}^{-2\pi\mathrm{i}\,\pmb{k}\cdot\pmb{x}}\]

with an index set $I_{\pmb{N}}^d \coloneqq \{ \pmb{k} \in \mathbb{Z}^d: -\frac{N_i}{2} \leq \pmb{k}_i \leq \frac{N_i}{2}-1, i=1,2,\ldots,d \}$ where $\pmb{N} \in (2\mathbb{N})^d$ is the multibandlimit, the nonequispaced fast Fourier transform (NDFT) is its evaluation at $M \in \mathbb{N}$ nonequispaced points $\pmb{x}_j \in \mathbb{T}^d$ for $j = 1,2, \ldots, M$,

\[ f(\pmb{x}_j) =\sum_{\pmb{k} \in I_{\pmb{N}}^d} \hat{f}_{\pmb{k}} \, \mathrm{e}^{-2 \pi \mathrm{i} \, \pmb{k} \cdot \pmb{x}_j},\]

with given coefficients $\hat{f}_{\pmb{k}} \in \mathbb{C}$ where we identify the smooth manifold of the torus $\mathbb{T}$ with $[-1/2, 1/2)$. The NFFT is an algorithm for the fast evaluation of the sums $f(\pmb{x}_j)$ as well as the adjoint problem, the fast evaluation of

\[ \hat{h}_{\pmb{k}} = \sum_{j = 1}^{M} f_j \, \mathrm{e}^{2 \pi \mathrm{i} \, \pmb{k} \cdot \pmb{x}_j}, \pmb{k} \in I_{\pmb{N}}^d,\]

for given coefficients $f_j \in \mathbb{C}$. The available NFFT3 library [Keiner, Kunis, Potts, NFFT3] provides C routines for the NFFT as well as applications such as the fast evaluation of sums

\[ g(\pmb{y}_j) \coloneqq \sum_{k=1}^{N} \alpha_k \, K(\lVert \pmb{y}_j - \pmb{x}_k \rVert_2), j = 1, \ldots, M,\]

for given coefficients $\alpha_k \in \mathbb{C}$, nodes $\pmb{x}_k,\pmb{y}_j \in \R^d$ and a radial kernel function $K: [0,\infty) \to [0,\infty)$, and generalizations such as the NNFFT for nonequispaced nodes in time and frequency domain.

The NFFT3 C library has been developed at the Mathematical Institute of the University of Luebeck, at the Mathematical Institute of the University Osnabrueck 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 have been done by Toni Volkmer, Michael Quellmalz, and Michael Schmischke.

This package offers a Julia wrapper for the NFFT, NFCT, NFST, and fastsum algorithms, see [Schmischke, 2018].

Literature