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
  • Beta release: 1D codes
  • Beta release: 2D codes
  • Alpha release: 3D codes
  • NUFFT Manual
  • License
  • Technical paper: Accelerating the Nonuniform Fast Fourier Transform
    (L. Greengard and J.-Y. Lee) SIAM Review 46, 443 (2004).
  • Bug reports, comments: for the moment, please send to L. Greengard (greengard [at]

  • 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