1 The Radix-2 Frameworks 1
1.1 Matrix Notation and Algorithms 2
1.2 The FFT Idea 11
1.3 The Cooley-Tukey Radix-2 Factorization 17
1.4 Weight and Butterfly Computations 22
1.5 Bit Reversal and Transposition 36
1.6 The Cooley-Tukey Framework 44
1.7 The Stockham Autosort Frameworks 49
1.8 The Pease Framework 60
1.9 Decimation in Frequency and Inverse FFTs 64
2 General Radix Frameworks 76
2.1 General Radix Ideas 76
2.2 Index Reversal and Transposition 84
2.3 Mixed-Radix Factorizations 95
2.4 Radix-4 and Radix-8 Frameworks 101
2.5 The Split-Radix Framework 111
3 High-Performance Frameworks 121
3.1 The Multiple DFT Problem 122
3.2 Matrix Transposition 125
3.3 The Large Single-Vector FFT Problem 139
3.4 The Multidimensional FFT Problem 148
3.5 Distributed-Memory FFTs 156
3.6 Shared-Memory FFTs 176
4 Selected Topics 188
4.1 Prime Factor Frameworks 188
4.2 Convolution 205
4.3 FFTs of Real Data 215
4.4 Fast Trigonometric Transforms 229
4.5 Fast Poisson Solvers 247
Bibliography 259
Index 269