# Non Uniform FFT / DFT with FFTW?

Can FFTW perform the FFT on data which is not uniform in time? I can't seem to find a straight-forward answer to this question anywhere online.

• Given my (limited) knowledge of how FFT works my instinct is no. I think the standard approach to this would be to resample so you are uniform in time. Although I'm not really an expert in FFTs so I may be wrong. May 29 '14 at 16:09
• Yeah, I'm aware that FFT requires uniform sampling, but I wasn't sure if FFTW included built-in functionality to realize when data was non-uniform and then apply a NUDFT.
– John
May 29 '14 at 16:21

## 1 Answer

The answer is Non-uniform discrete Fourier transform

I suggest you to take a look in here: NFFT library. Tutorial for that purpose: NFFT 3.0 Tutorial.

You can also find a Python wrapper: pyNFFT.

The generalisations of the NFFT include

NNFFT - nonequispaced in time and frequency fast Fourier transform,

NFCT/NFST - nonequispaced fast (co)sine transform,

NSFFT - nonequispaced sparse fast Fourier transform,

FPT - fast polynomial transform,

NFSFT - nonequispaced fast spherical Fourier transform,

NFSOFT - nonequispaced fast Fourier transform on the rotation group

The NFFT is a C subroutine library for computing the nonequispaced discrete Fourier transform (NDFT) in one or more dimensions, of arbitrary input size, and of complex data. New: A Matlab interface is part of the NFFT3. We believe that our library, which is free software, and based on FFTW (FFTW 3.x) should become the NFFT library of choice for most applications.

• Thanks. I've actually been looking into this one, but I haven't been able to get it to work properly and was hoping I could just make FFTW work instead.
– John
May 29 '14 at 16:19
• I believe that FFTW has no such functionality. For me tutorial was fairly straightforward and had no problems with using NFFT back in time. Just take a look into Chapter 5.
– jojek
May 29 '14 at 16:22
• Does the library plug and play on Windows? The guides seem to target Linux OS, so when I couldn't get it to install properly I assumed that this was to blame.
– John
May 29 '14 at 16:23
• Yep, It does. Just follow steps described here.
– jojek
May 29 '14 at 16:25
• And if I don't wish to use MATLAB but rather MSVC or some other c++ editor?
– John
May 29 '14 at 16:26