NFFT
NFFT
NFFT
a preliminary version 3.0.0 is now available, 10 may 2006

Introduction

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

The NFFT approximates

$\displaystyle f_j = \sum_{\mbox{\boldmath\scriptsize {${k}$}}\in I_{\mbox{\bold... ...riptsize {${k}$}}\mbox{\boldmath\scriptsize {${x}$}}_j} \qquad (j=0,\hdots,M-1)$    
its adjoint/transposed
$\displaystyle \hat{f}_{\mbox{\boldmath\scriptsize {${k}$}}} = \sum_{j=0}^{M-1} ... ...x}$}}_j} \qquad (\mbox{\boldmath {${k}$}}\in I_{\mbox{\boldmath\tiny {${N}$}}})$    
and solves the inverse ndft
$\displaystyle \sum_{\mbox{\boldmath\scriptsize {${k}$}}\in I_{\mbox{\boldmath\t... ...k}$}}\mbox{\boldmath\scriptsize {${x}$}}_j} \approx f_j \qquad (j=0,\hdots,M-1)$    
for arbitrary sampling sets $ {\cal X}:=\left\{\mbox{\boldmath {${x}$}}_j:\,j=0,\hdots,M-1\right\}\subset \mathbb{T}^d$

The NFFT package was developed at the Mathematical Institute of the University of Lübeck and at the Faculty of Mathematics of the Chemnitz University of Technology by Stefan Kunis and Daniel Potts.

Version 2 - features

The latest version is 2.0.3. The API of NFFT 2.x is incompatible with that of NFFT 1.x. Here is a list of some of NFFT's more interesting features:

  • Implemented transforms for one and more dimensions.
  • Iterative solution of the inverse transform.
  • Arbitrary-size transforms.
  • Works on any platform with a C compiler and the FFTW package.
  • Simple and flexible interface, 'type safety' and easy adaptability.
  • Options (determined at compile time) and parameters (determined at run time).

Documentation

You can read the NFFT 2.0 manual online (also available, in the NFFT package, are PostScript and Acrobat PDF versions of the documentation).

The most current general paper, and the one that we recommend if you wish to cite NFFT, is:

A tutorial on NFFT was published in the 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. on Sci. Comput. 24, 2013-2037. (full paper ps, pdf),   2003

The inverse NFFT is considered in Stability Results for Scattered Data Interpolation by Trigonometric Polynomials ( full paper ps, pdf).

Some papers about NFFT are available online. For general questions about non equispaced discrete Fourier transforms, see our links to NFFT-related resources.

Examples of usage including recent examples in papers are given here.

Downloading

Download version 2.0.3 of NFFT (also available .tar.gz). Feel free to post NFFT on your own site, but be sure to tell us so that we can link to your page and inform you about updates to the software.

Version 1.0

The version 1.0 of the library can be downloaded here. Use the NFFT 1.0 manual online, PostScript and Acrobat PDF versions of the documentation.

Feedback

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

counter

University News

Social Media

Connect with Us: