The type 3 nonuniform FFT and its applications

June Yub Lee, Leslie Greengard

Research output: Contribution to journalArticlepeer-review


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 (US)
Pages (from-to)1-5
Number of pages5
JournalJournal of Computational Physics
Issue number1
StatePublished - Jun 10 2005


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

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


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

Cite this