NUFFT, NFFT, USFFT

Implements 1D-3D NUFFTs via "Fast Gaussian Gridding."

Description

The Matlab code in this folder implements 1D-3D NUFFTs via fast Gaussian gridding. The convolution loops are written as C programs to be compiled as mex files from the Matlab command prompt. Further mathematical details about the code can be found in L. Greengard and J. Lee, "Accelerating the Nonuniform Fast Fourier Transform," SIAM Review, Vol. 46, No. 3, pp. 443-454.

I have included three example scripts (fgg_1D_experiment.m, etc)that create a simple 1D/2D/3D image and compare the DFT with the Type-I NUFFT (DFT from nonuniform data to uniform image grid). The image data are transformed back to the data domain via the adjoint operator (a Type-II NUFFT--uniform grid DFTed to nonuniform data locations--implemented with IFFTs instead of FFTs) and back again to the image domain to demonstrate the numerical accuracy. This code does not include Type-III transforms (nonuniform-->nonuniform), but one could easily be developed by combining the Type-I and Type-II functions provided here.

Before running any of the test scripts, remember to compile the mex files in the Matlab terminal by executing these commands:
mex FGG_Convolution1D.c
mex FGG_Convolution1D_type2.c
mex FGG_Convolution2D.c
mex FGG_Convolution2D_type2.c
mex FGG_Convolution3D.c
mex FGG_Convolution3D_type2.c

If you publish anything that uses this code, we ask that you please reference the source, as this will encourage future funding for more free Air Force Research Laboratory (AFRL) products. This code was developed through the Air Force Office of Scientific Research (AFOSR) Lab Task "Moving-Target Radar Feature Extraction."
Project Manager: Arje Nachman
Principal Investigator: Matthew Ferrara

• MATLAB release: MATLAB 7.6 (R2008a)
• Other requirements: c compiler

Other Files

license.txt,
NUFFT_code/license.txt,
NUFFT_code/NUFFT_code/fgg_1D_experiment.m,
NUFFT_code/NUFFT_code/FGG_1d_type1.m,
NUFFT_code/NUFFT_code/fgg_2D_experiment.m,
NUFFT_code/NUFFT_code/FGG_2d_type1.m,
NUFFT_code/NUFFT_code/fgg_3D_experiment.m,
NUFFT_code/NUFFT_code/FGG_3d_type1.m,
NUFFT_code/NUFFT_code/FGG_Convolution1D.c,
NUFFT_code/NUFFT_code/FGG_Convolution1D_type2.c,
NUFFT_code/NUFFT_code/FGG_Convolution2D.c,
NUFFT_code/NUFFT_code/FGG_Convolution2D_type2.c,
NUFFT_code/NUFFT_code/FGG_Convolution3D.c,
NUFFT_code/NUFFT_code/FGG_Convolution3D_type2.c,
NUFFT_code/NUFFT_code/iFGG_1d_type2.m,
NUFFT_code/NUFFT_code/iFGG_2d_type2.m,
NUFFT_code/NUFFT_code/iFGG_3d_type2.m

[Cris Luengo]

Matthew, you are not a "Principle Investigator" unless you investigate principles. You should spell that "principal".

This is a very interesting submission, I'm going to give a look. Thanks!