Jump to main content
Nonequispaced fast Fourier transform


You can read the NFFT Tutorial, as well as the NFFT 3.5 Doxygen Documentation (pdf), which gives detailed information on more advanced options and parameter settings for each routine.

The general paper, that we recommend if you wish to cite NFFT, is:

Keiner, J., Kunis, S., and Potts, D. Using NFFT 3 - a software library for various nonequispaced fast Fourier transforms ACM Trans. Math. Software, 36, Article 19, 1-30, 2009, (full paper ps, pdf).

The technical report OpenMP parallelization in the NFFT software library was written by Toni Volkmer. A tutorial on NFFT was published in 2001 in: Modern Sampling Theory: Mathematics and Applications, J.J. Benedetto and P. Ferreira (Eds.), Chapter 12, pages 249-274 with the title 'Fast Fourier transforms for nonequispaced data: A tutorial' (also in ps, pdf), by D. Potts, G. Steidl, and M. Tasche.

Or the appendix in Potts, D. and Steidl, G. Fast summation at nonequispaced knots by NFFTs. SIAM J. Sci. Comput. 24, 2013-2037. (full paper ps, pdf),   2003

The inverse NFFT is considered by S. Kunis and D. Potts in Stability Results for Scattered Data Interpolation by Trigonometric Polynomials, SIAM J. Sci. Comput. 29, 1403 - 1419,   (full paper ps, pdf).

Detailed information of the NFFT is given by S. Kunis and D. Potts in Time and memory requirements of the Nonequispaced FFT, Sampling Theory in Signal and Image Processing 7, 77 - 100, (full paper ps, pdf).

Some papers about NFFT are available online. Furthermore see the thesis by S. Kunis Nonequispaced FFT - Generalisation and Inversion (full thesis pdf).

An overview about the discrete Fourier transform and its generalizations is provided in the textbook by G. Plonka, D. Potts, G. Steidl, and M. Tasche: Numerical Fourier Analysis (2019), ANHA, Birkhäuser, ISBN 978-3-030-04305-6,   (available via Springer or Springer-online).