*(English)*Zbl 0757.65154

The fast Fourier transform (FFT) is one of the important computational developments of this century. It has revolutionized many areas of scientific computation. Today we know many books on the FFT often written by specialists in computer science, digital signal processing or electrical engineering. The new book is written by a known researcher in numerical linear algebra. The central theme of the author is the idea that different FFTs correspond to different factorizations of the Fourier matrix into a product of sparse matrices which can often be represented as Kronecker products. Couching algorithms systematically in matrix/vector notation, the FFTs can be unified and described more understandable. All algorithms are written in a stylized Matlab notation which is familiar to those engaged in high-performance computing.

This book contains 4 chapters. The first chapter is devoted to the basic principles of radix-2 FFTs, namely Cooley-Tukey factorization, weight and butterfly computations, bit reversal and transposition, Cooley-Tukey algorithm, Stockham autosort algorithm, decimation in time, decimation in frequency.

Chapter 2 on mixed-radix FFTs generalizes the factorization ideas developed in Chapter 1. Especially, radix-4 and radix-8 FFTs are discussed. The split-radix FFT is handled as an interesting reduced- arithmetic rearrangement of the radix-2 FFT.

Chapter 3 is devoted to multidimensional FFTs and related topics. Here the author also describes the blocking of large single vector FFT and parallel FFTs ( distributed-memory FFT and shared-memory FFT).

In the final chapter some extensions ( prime factor FFT, FFTs of real data) and some essential FFT-applications ( convolutions, fast trigonometric transforms, fast Poisson solvers) are discussed.

This comprehensive book contains may examples, problems, notes and hints to the literature. It will be very useful for students as well as researchers who are interested in the application of the FFT.

##### MSC:

65T50 | Discrete and fast Fourier transforms (numerical methods) |

65-02 | Research monographs (numerical analysis) |

65F30 | Other matrix algorithms |

42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |

65F50 | Sparse matrices (numerical linear algebra) |