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.

Spis treści:
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.