Numerical Fourier analysis (Q1755632)

This textbook gives a state-of-the-art survey of practical numerical aspects of Fourier analysis in a classical sense. To make the book self-contained, the first four chapters recall (with full proofs for most of the theorems) the classical theory of Fourier series, the Fourier transform, the discrete Fourier transform (DFT), and the multidimensional extensions. In Chapter 5 the authors deal with several implementations of fast Fourier transforms (FFT) with analysis of complexity and numerical stability. There are several versions of the classical radix-2 implementations and its variants, but also Rader and Bleustein versions, the more recent sparse algorithms, and some multidimensional versions (based on tensor products). The literature is quite extensive on this subject and some FFT methods are only mentioned briefly (Groetzel, Bruun, cyclotonic FFT,\dots). The discrete cosine transform (DCT), which is directly related to Chebyshev polynomials and Chebyshev series, gets its own separate chapter. Interpolation in zeros and extremes can be obtained by barycentric formulas, FFT, or orthogonal matrix factorization, and that leads to (Clenshaw-Curtis) quadrature, and orthogonal polynomial expansions. In practical situations, data may not always be equispaced, which require adaptations to the FFT algorithms. Here the discussion switches back to the multivariate case. The idea is that the missing data in the time domain can be approximately recovered from equispaced data in the frequency domain and vice versa, using a sliding window. The general case is a combination of both. An application can be a fast matrix vector multiplication. The inverse problem is then the approximate solution of a linear system. For high-dimensional FFT, an approximate FFT is computed based on the samples taken on rank-1 lattices which are interpolated by a trigonometric polynomial. Construction of the polynomial and its evaluation are implemented efficiently. The DFT has many applications, and several of these are discussed in more detail. These include interpolation by translation of B-splines and other basic functions, possibly with attenuation factors, numerical quadrature of periodic functions, acceleration of convergence of Fourier series (Krylov-Lanczos techniques), fast Poisson solvers, and spherical Fourier transforms. Prony-type methods have many applications and deserve a separate chapter. The problem is to recover a linear combination of an unknown number of real and/or complex exponentials from noisy data. A detailed discussion is given for the case of the frequency analysis problem (only complex exponentials). MUSIC, APM, and ESPRIT are popular methods for parameter estimation, and algorithms are proposed using these techniques. Applications include the recovery of a function with known shape from noisy data and phase reconstruction. The text is carefully compiled, including the classical results, but also the most recent ones like the sparse FFT, the FFT using lattices and the recent insights into Prony-type methods. Although part of the text appeared earlier in German as lecture notes, there are no exercises in this book. It is more a reference work with an extensive list of references, but parts of it can be selected to serve as lecture notes. The computer code for some of the algorithms is available from public github sites, but there is not a common website collecting everything. You should contact the authors. Although there are four authors, the terminology and notation is remarkably consistent throughout the book, so that a glossary of terms, notation, and acronyms as well as the extensive subject index is very welcome.