Introduction

This technical report gives a short summary of the fast Fourier transform at non equispaced knots (NFFT) and its generalised inverse. An introduction to the NFFT, error estimates etc. can be found in [20]. The computational complexity of the proposed algorithms is ${\cal O}\left(N_{\text{\tiny $\Pi$}} \log N_{\text{\tiny $\Pi$}} + M\right)$ for $N_{\text{\tiny $\Pi$}}$ equispaced frequencies and $M$ non equispaced samples.

The algorithms are implemented in the C-library nfft2 which will be described in detail. The heart of the algorithms are (uniform) fast Fourier transforms for which the library fftw3 (see [12]) is used.

The remainder is organised as follows: in Section 2, the problems of the discrete Fourier transform at non equispaced knots (NDFT) are stated, the used notation is introduced, related works are classified, and the fast algorithm (NFFT) is deduced in pseudo code. Furthermore, an iterative scheme for inversion of the NFFT is presented. The implementation and usage of the library is described in Section 3. Finally, simple examples of usage and numerical results are presented in Section 4.