The type 3 nonuniform FFT and its applications

June Yub Lee, Leslie Greengard

Research output: Contribution to journalArticlepeer-review

142 Scopus citations


The nonequispaced or nonuniform fast Fourier transform (NUFFT) arises in a variety of application areas, including imaging processing and the numerical solution of partial differential equations. In its most general form, it takes as input an irregular sampling of a function and seeks to compute its Fourier transform at a nonuniform sampling of frequency locations. This is sometimes referred to as the NUFFT of type 3. Like the fast Fourier transform, the amount of work required is of the order O(N log N), where N denotes the number of sampling points in both the physical and spectral domains. In this short note, we present the essential ideas underlying the algorithm in simple terms. We also illustrate its utility with application to problems in magnetic resonance imagin and heat flow.

Original languageEnglish
Pages (from-to)1-5
Number of pages5
JournalJournal of Computational Physics
Issue number1
StatePublished - 10 Jun 2005

Bibliographical note

Funding Information:
This work was supported by the Applied Mathematical Sciences Program of the US Department of Energy under Contract DEFGO200ER25053.


  • Fourier integral
  • Heat equation
  • Magnetic resonance imaging
  • Nonuniform fast Fourier transform


Dive into the research topics of 'The type 3 nonuniform FFT and its applications'. Together they form a unique fingerprint.

Cite this