File Exchange

image thumbnail


version 1.2 (47.8 KB) by

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



View License

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

Comments and Ratings (15)

Maciej Wielgo

I had the same problem as Ahmed Fasih, for me this software just doesnt work with non-uniform samples in 1D case (the outcome is incorrect). Have not tried 2D and 3D.

Hi everyone,

I encountered the same problem as David Craig, using MATLAB Version (R2013a) on Ubuntu 16.04 LTS.

I followed Ahmed Fasih's advice and it worked. Thank you Ahmed.

hao wang

Good,it's helpful.
But it is a pity that the type-3 is absent!

Robin Martin

But there are some problems left to fix

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?????!!!!

Ahmed Fasih

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

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,

David Craig

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

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


Apple (view profile)

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


David (view profile)

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


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 * /

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

kk KKsingh

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

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!



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

MATLAB Release
MATLAB 7.6 (R2008a)

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

» Watch video