File Exchange

image thumbnail

NUFFT, NFFT, USFFT

version 1.2.0.0 (47.8 KB) by Matthew Ferrara
Implements 1D-3D NUFFTs via "Fast Gaussian Gridding."

51 Downloads

Updated 13 Oct 2009

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 (21)

Hello,

Can anyone tell me how to calculate time index of the data after performing non uniform IFFT using the provided functions ?
In what unit will the time index be ? I have data as channel state information of 30 non- uniformly spaced subcarriers of 20 MHz wifi band which is obviously frequency domain. After using non uniform IFFT, i convert them to time domain data . Now I want to find the value of time index and its unit.

Any help would be appreciated.

Regards,
Sandeep

Fred Stanke

In fgg_1D_experiment.m, I do not see any use of non-uniform gridding.
knots is uniformly sampled for all these calls:
MattOut_Gauss=FGG_1d_type1(data(:),knots,[Nx],Desired_accuracy);
MattOut_T2=iFGG_1d_type2(MattOut_Gauss,knots,Desired_accuracy);
MattOut_Gauss2=FGG_1d_type1(MattOut_T2(:),knots,[Nx],Desired_accuracy);
So where is "a Type-II NUFFT--uniform grid DFTed to nonuniform data locations"?

toutou

toutou (view profile)

Neil Salmon

I’m working on aperture synthesis imaging and I’m looking for a routine to replace the 3D analytic FT I already use to do FT’s on non-uniform sampled data.

I see there are a number of groups working on NUFFT’s, eg that from Jeffrey Fessler, but his is quite a large package with loads of stuff, CT, MRI etc.

I note the Matlab Website says for the NUFFT it’s updated 13 Oct 2009, and Matthew Ferraro has is email at WPAB, no longer responds to emails, so if given passage of time whether Fessler's code is superior, or as far as the basic UNFFT algorithm it is much the same.

https://uk.mathworks.com/matlabcentral/fileexchange/25135-nufft--nfft--usfft

Yours on the Matlab Website appears much simpler and easier to use, Jeffery’s on the other hand appear newer and might be more efficient and faster.

Could anyone say if the NUFFT engine you present on the Matlab website is no less efficient than that on the Jeffrey’s website?

Many thanks,
Neil

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 8.1.0.604 (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

Good
But there are some problems left to fix

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

eg:
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:
http://www.mathworks.com/support/compilers/current_release/

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,
Thanks
Dave

David Craig

should have mentioned I use MATLAB Version 7.12.0.635 (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

Apple (view profile)

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

David

David (view profile)

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

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

kk KKsingh

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

kk KKsingh

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

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!

Updates

1.2.0.0

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

MATLAB Release Compatibility
Created with R2008a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.


Learn About Live Editor