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.