View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from

3.3 | 3 ratings Rate this file 41 Downloads (last 30 days) File Size: 47.8 KB File ID: #25135 Version: 1.2



Matthew Ferrara (view profile)


25 Aug 2009 (Updated )

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

| Watch this File

File Information

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
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (12)
10 Dec 2014 Robin Martin

But there are some problems left to fix

25 Jan 2013 No.2006, Xiyuan Ave, West Hi-Tech Zone No.2006, Xiyuan Ave, West Hi-Tech Zone

hi,i have problems with the 1D example,i cant get the right reslut.

F = FGG_1d_type1(f,knots,N,accuracy,GridListx)
the input data is nonuniformly-spaced frequency data?????!!!!

Comment only
08 Jan 2013 Ahmed Fasih

@David Craig, replace "//" C++-style comments in the offending files with "/* ... */" comments.

Comment only
17 Nov 2012 David Craig

Hi, I am having trouble compiling two of the .c files,
mex FGG_Convolution1D_type2.c
mex FGG_Convolution2D
give the following error,
>> mex FGG_Convolution1D_type2.c

Warning: You are using gcc version "4.6.3-1ubuntu5)". The version
currently supported with MEX is "4.3.4".
For a list of currently supported compilers see:

FGG_Convolution1D_type2.c: In function ‘mexFunction’:
FGG_Convolution1D_type2.c:67:16: warning: assignment discards ‘const’ qualifier from pointer target type [enabled by default]
FGG_Convolution1D_type2.c:69:16: warning: assignment discards ‘const’ qualifier from pointer target type [enabled by default]
FGG_Convolution1D_type2.c:71:16: warning: assignment discards ‘const’ qualifier from pointer target type [enabled by default]
FGG_Convolution1D_type2.c:72:5: error: expected expression before ‘/’ token
FGG_Convolution1D_type2.c:75:18: warning: assignment discards ‘const’ qualifier from pointer target type [enabled by default]

mex: compile of ' "FGG_Convolution1D_type2.c"' failed.

??? Error using ==> mex at 208
Unable to complete successfully.

Anyone seen this before,

Comment only
17 Nov 2012 David Craig

should have mentioned I use MATLAB Version (R2011a) on ubuntu 12.04

Comment only
28 Jun 2012 Ahmed Fasih

I tried getting the 1D example (forward and adjoint operators) to work with non-uniform samples and, after editing the Matlab function, got the forward transform half-way working before I gave up. The algorithm, used as instructed by the documentation, does not produce correct results as is. (Correctness is in comparison with the direct computation of the non-uniform DFT.)

07 Dec 2011 Apple

Apple (view profile)

This doesn't work for 3D non-Cartesian MRI k-space trajectory.

Comment only
21 Jul 2011 David

David (view profile)

Could you please clarify which routine goes from non-uniform spatial grid to uniform spatial grid? Thanks for the submission.

Comment only
24 Jun 2011 bmv

bmv (view profile)

fix some C files please
Need to properly close the comments:
/ * Copy input pointer Scales_point
should be:
/ * Copy input pointer Scales_point * /

28 Feb 2010 kk KKsingh

In your code you said on request you can submit the code by Liu, can you submit it will be good for comparision and study purpose

Comment only
11 Feb 2010 kk KKsingh

Its not working for me, worked for some one or not

Comment only
10 Oct 2009 Cris Luengo

Cris Luengo (view profile)

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!

Comment only
13 Oct 2009 1.2

Bug was fixed in 2D code. Grammatical error fixed in notes (thanks, Cris).

Contact us