Fast Fourier-Based Algorithms in Different Kinds of Applications

The fast Fourier transform (FFT) is one of the most important methods in data and signal processing. It can be used to efficiently evaluate trigonometric polynomials on equidistant grids, where the number of required arithmetic operations only increases like O(N log N), where N denotes the grid size.
In many applications, however, arbitrarily distributed data points are given instead of equidistant grids. In order to be able to work efficiently with trigonometric polynomials for such data, the so-called FFT for nonequispaced data (NFFT) can be used.
The spectrum of applications ranges from fast summation methods, the calculation of interactions in particle systems and methods for high-dimensional approximation to (kernel-based) methods in the field of machine learning.
In this talk, we will focus on NFFT and related fast summation methods. After an introduction of these methods, we focus on some selected applications.