Home People Software Projects Alumni Links

NUFFT (NFFT, USFFT) Software

Fourier analysis plays a natural role in a wide variety of applications, from medical imaging to radio astronomy, data analysis and the numerical solution of partial differential equations. When the sampling is uniform and the Fourier transform is desired at equispaced frequencies, the classical fast Fourier transform (FFT) has played a fundamental role in computation.

The FFT requires O(N log N) work to compute N Fourier modes from N data points rather than O(N2) work.

When the data is irregular in either the "physical" or "frequency" domain, unfortunately, the FFT does not apply. Over the last twenty years, a number of algorithms have been developed to overcome this limitation - generally referred to as non-uniform FFTs (NUFFT), non-equispaced FFTs (NFFT) or unequally-spaced FFTs (USFFT). They achieve the same O(N log N) computational complexity, but with a larger, precision-dependent, and dimension-dependent constant.

We have developed some NUFFT libraries in Fortran 77 and Fortran 90 that are freely available under the GPL license.

Downloads and documentation:
  • Version 1 (GPL license): 1D codes
  • Version 1 (GPL license): 2D codes
  • Version 1 (GPL license): 3D codes
  • NUFFT Manual
  • GPL License
  • Bug reports, comments: for the moment, please send to L. Greengard (greengard [at] cims.nyu.edu)
  • Please acknowledge the NUFFT package in programs or publications in which you use the code. We suggest as references:

    [1] Accelerating the Nonuniform Fast Fourier Transform: (L. Greengard and J.-Y. Lee) SIAM Review 46, 443 (2004).
    [2] The type 3 nonuniform FFT and its applications: (J.-Y. Lee and L. Greengard) J. Comput. Phys. 206, 1 (2005).

    For the original NUFFT paper, see

    Fast Fourier Transforms for Nonequispaced data: (A. Dutt and V. Rokhlin) SIAM J. Sci. Comput. 14, 1368 (1993).

    LATEST RELEASE: includes MATLAB interfaces (fixed MATLAB incompatibility for Mac OS X: 8/04/2014)

  • Version 1.3.2 (FreeBSD license): 1D codes
  • Version 1.3.2 (FreeBSD license): 2D codes
  • Version 1.3.2 (FreeBSD license): 3D codes
  • NUFFT Manual

  • Some Other NUFFT libraries
  • NFFT from Chemnitz University of Technology)
  • NUFFT and Image Reconstruction Software from U. Michigan
  • NUFFT Software via MATLAB Central from Air Force Research Lab, Wright-Patterson AFB