The type 3 nonuniform FFT and its applications

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computational physics 2005-06, Vol.206 (1), p.1-5
Main Authors: Lee, June-Yub, Greengard, Leslie
Format: Article
Language:English
Subjects:
Computational techniques
Exact sciences and technology
Fourier integral
Fourier transforms
Heat equation
Heat transmission
Magnetic resonance imaging
Mathematical analysis
Mathematical methods in physics
Mathematical models
Nonuniform
Nonuniform fast Fourier transform
Physics
Sampling
Spectra
Utilities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0021-9991
1090-2716
DOI:10.1016/j.jcp.2004.12.004