Non Uniform FFT / DFT with FFTW?
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.