Are some areas of fast Fourier transforms still unclear to you? Do the notation and vocabulary seem inconsistent? Does your knowledge of their algorithmic aspects feel incomplete? The fast Fourier transform represents one of the most important advancements in scientific and engineering computing. Until now, however, treatments have been either brief, cryptic, intimidating, or not published in the open literature. Inside the FFT Black Box brings the numerous and varied ideas together in a common notational framework, clarifying vague FFT concepts.
Examples and diagrams explain algorithms completely, with consistent notation. This approach connects the algorithms explicitly to the underlying mathematics. Reviews and explanations of FFT ideas taken from engineering, mathematics, and computer science journals teach the computational techniques relevant to FFT. Two appendices familiarize readers with the design and analysis of computer algorithms, as well.
This volume employs a unified and systematic approach to FFT. It closes the gap between brief textbook introductions and intimidating treatments in the FFT literature. Inside the FFT Black Box provides an up-to-date, self-contained guide for learning the FFT and the multitude of ideas and computing techniques it employs.
Table of Contents
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
Fundamental Concepts of Efficient Scientific Computation
Solving Recurrence Equations by Substitution
"…this book will serve as a self-teaching guide for learning not only FFT, but also many widely applicable techniques in algorithm design and analysis, efficient numerical computation, and scientific programming."