Introduction

This tutorial surveys the fast Fourier transform at nonequispaced nodes (NFFT), its generalisations, its inversion, and the related C library NFFT 3.0. The goal of this manuscript is twofold - to shed some light on the mathematical background, as well as to provide an overview over the C library to allow the user to use it effectively. Following this, this document splits into two parts:

In Sections 2, 3 and 3.6, we introduce the NFFT which, as a starting point, leads to several concepts for further generalisation and inversion. We focus on a mathematical description of the related algorithms. However, we complement the necessarily incomplete quick glance at the ideas by references to related mathematical literature. In Section 2, we introduce the problem of computing the discrete Fourier transform at nonequispaced nodes (NDFT), along with the notation used and related works in the literature. The algorithms (NFFT) are developed in pseudo code. Furthermore, we turn for recent generalisations, including in particular NFFTs on the sphere and iterative schemes for inversion of the nonequispaced FFTs, in Section 3 and 3.6, respectively.

Having laid the theoretical foundations, Section 4 provides an overview over the NFFT 3.0 C library and the general principles for using the available algorithms in your own code. Rather than describing the library interface in every detail, we restrict to simple recipes in order to familiarise with the very general concepts sufficient for most everyday tasks. For the experienced user, we provide full interface documentation (see doc/html/index.html in the package directory) which gives detailed information on more advanced options and parameter settings for each routine. Figure gives an overview over the directory structure of the NFFT 3.0 package. Finally, Section 5 gives some simple examples for using the library and some more advanced applications are given in Section 6 along with numerical results.