Nonequispaced fast Fourier transform
Time and frequency nonequispaced
Nonequispaced fast Fourier transform  

NNFFT - Fourier transform with non equispaced data in time and frequency domain

This library of C functions computes approximations of sums of the form $$ d_j := \sum\limits_{l=1}^{L-1} \alpha_l\, {\rm {e}}^{2\pi \mathrm{i} (k_l\odot N)x_j} \quad (j =1,\ldots,M) $$ with \(k_l, x_j \in [-1/2,1/2)^d\) and \(\alpha_l \in \mathbb{C}\).
 

The algorithms are implemented by Tobias Knopp in ./examples/nnfft Related paper are

  • Keiner, J., Kunis, S., and Potts, D.
    Using NFFT 3 - a software library for various nonequispaced fast Fourier transforms
    ACM Trans. Math. Software, 36, Article 19, 1-30, (full paper ps, pdf)   2009
     
  • Potts, D., Steidl G., and Tasche M.
    Fast Fourier transforms for nonequispaced data: A tutorial.
    In: Modern Sampling Theory: Mathematics and Applications, J.J. Benedetto and P. Ferreira (Eds.), Chapter 12, pages 249-274. (full paper ps.Z, pdf),   1998