Fast Fourier Methods for Trigonometric Polynomials and Bandlimited Functions

The well-known fast Fourier transform (FFT) is one of the most important and widely used algorithms in a multitude of disciplines including engineering, natural sciences, scientific computing, and signal processing. Nevertheless, its restriction to equispaced data represents a significant limitation in practice. Consequently, this has led to the development of the nonequispaced fast Fourier transform (NFFT), which permits the use of arbitrary nodes in the spatial domain.
In a variety of applications, such as magnetic resonance imaging (MRI), solution of partial differential equations (PDEs), etc., however, there is a need for the inverse transform, i.e., computing Fourier data from given nonequispaced function evaluations of trigonometric polynomials, or even of bandlimited functions. For this reason, this thesis focuses on the presentation of new efficient inversion methods for the NFFT, which can be realized with the complexity of a single NFFT, and on the generalization of these methods to the setting of bandlimited functions. Additionally, the evaluation problem for bandlimited functions is addressed as well. In particular, the present thesis provides the first comprehensive overview of the so-called regularized Shannon sampling formulas.