Computational Frameworks for the Fast Fourier Transform

The most comprehensive treatment of FFTs to date. Van Loan captures the interplay between mathematics and the design of effective numerical algorithms--a critical connection as more advanced machines become available. A stylized Matlab notation, which is familiar to those engaged in high-performance computing, is used. The Fast Fourier Transform (FFT) family of algorithms has revolutionized many areas of scientific computation. The FFT is one of the most widely used algorithms in science and engineering, with applications in almost every discipline. This volume is essential for professionals interested in linear algebra as well as those working with numerical methods. The FFT is also a great vehicle for teaching key aspects of scientific computing.

1. The Radix-2 Frameworks. Matrix Notation and Algorithms; The FFT Idea; The Cooley-Tukey Factorization; Weight and Butterfly Computations; Bit Reversal and Transposition; The Cooley-Tukey Framework; The Stockham Autosort Frameworks; The Pease Framework; Decimation in Frequency and Inverse FFTs; 2. General Radix Frameworks. The General Radix Ideas; Index Reversal and Transposition; Mixed-Radix Factorizations; Radix-4 and Radix-8 Frameworks; The Split-Radix Frameworks; 3. High Performance Frameworks. The Multiple DFT Problem; Matrix Transposition; The Large Single-Vector FFT Problem; Multi-Dimensional FFT Problem; Distributed Memory FFTs; Shared Memory FFTs; 4. Selected Topics. Prime Factor FFTs; Convolution; FFTs of Real Data; Cosine and Sine Transforms; Fast Poisson Solvers; Bibliography; Index.

he Fast Fourier Transform family of algorithms has revolutionized many areas of scientific computation. The FFT is one of the most widely used algorithms in science and engineering, with applications in almost every discipline. Essential reading for professionals interested in linear algebra as well as those working with numerical methods.