Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms (Hardcover)

PRELIMINARIES
An Elementary Introduction to the Discrete Fourier Transform
Some Mathematical and Computational Preliminaries
SEQUENTIAL FFT ALGORITHMS
The Divide-and-Conquer Paradigm and Two Basic FFT Algorithms
Deciphering the Scrambled Output from In-Place FFT Computation
Bit-Reversed Input to the Radix-2 DIF FFT
Performing Bit-Reversal by Repeated Permutation of Intermediate Results
An In-Place Radix-2 DIT FFT for Input in Natural Order
An In-Place Radix-2 DIT FFT for Input in Bit-Reversed Order
An Ordered Radix-2 DIT FFT
Ordering Algorithms and Computer Implementation of Radix-2 FFTs
The Radix-4 and the Class of Radix-2s FFTs
The Mixed-Radix and Split-Radix FFTs
FFTs for Arbitrary N
FFTs for Real Input
FFTs for Composite N
Selected FFT Applications
PARALLEL FFT ALGORITHMS
Parallelizing the FFTs: Preliminaries on Data Mapping
Computing and Communications on Distributed-Memory Multiprocessors
Parallel FFTs without Inter-Processor Permutations
Parallel FFTs with Inter-Processor Permutations
A Potpourri of Variations on Parallel FFTs
Further Improvement and a Generalization of Parallel FFTs
Parallelizing Two-Dimensional FFTs
Computing and Distributing Twiddle Factors in the Parallel FFTs
APPENDICES
Fundamental Concepts of Efficient Scientific Computation
Solving Recurrence Equations by Substitution
Bibliography