The type 3 nonuniform FFT and its applications

June Yub Lee, Leslie Greengard

Research output: Contribution to journalArticlepeer-review

121 Scopus citations

Abstract

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
Volume206
Issue number1
DOIs
StatePublished - 10 Jun 2005

Keywords

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

Fingerprint

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

Cite this