Inside the FFT Black Box Serial and Parallel FFT Algorithms

Inside FFT Black Box: Serial & Parallel FFT Algorithms......Page 1
Copyright......Page 4
Contents......Page 5
Preface......Page 12
Part I Preliminaries......Page 16
1.1 Complex Numbers......Page 17
1.2 Trigonometric Interpolation......Page 19
1.3 Analyzing Series......Page 22
1.4 Fourier Frequency versus Time Frequency......Page 23
1.5 Filtering Signal......Page 24
1.6 How Often does One Sample?......Page 25
1.7 Notes & References......Page 26
Ch2 Some Mathematical & Computational Preliminaries......Page 27
2.1 Computing Twiddle Factors......Page 28
2.2.1 Real Floating-Point Operation (FLOP) Count......Page 29
2.2.2 Special Considerations in Computing FFT......Page 30
2.4 Solving Recurrences to Determine an Unknown Function......Page 31
Ch3 Divide-&-Conquer Paradigm & 2 Basic FFT Algorithms......Page 34
3.1 Radix-2 Decimation-in-Time (DIT) FFT......Page 35
3.1.1 Analyzing Arithmetic Cost......Page 36
3.2 Radix-2 Decimation-in-Frequency (DIF) FFT......Page 37
3.3 Notes & References......Page 38
Part II Sequential FFT Algorithms......Page 39
Ch4 Deciphering Scrambled Output from In-Place FFT Computation......Page 40
4.1 Iterative Form of Radix-2 DIF FFT......Page 41
4.2 Applying Iterative DIF FFT to a N = 32 Example.......Page 43
4.3 Storing & Accessing Pre-Computed Twiddle Factors......Page 45
4.4.2 Deciphering Scrambled Output......Page 47
4.5 Shorthand Notation for Twiddle Factors......Page 50
Ch5 Bit-Reversed Input to Radix-2 DIF FFT......Page 51
5.1 Effect of Bit-Reversed Input......Page 52
5.3 Shorthand Notation for DIF RN Algorithm......Page 54
5.3.2 Applying Algorithm 5.2 to a N = 32 Example.......Page 55
5.5 Notes & References......Page 57
Ch6 Performing Bit-Reversal by Repeated Permutation of Intermediate Results......Page 58
6.1.1 Ordered Radix-2 DIF NN FFT......Page 59
6.2 Applying Ordered DIF FFT to N = 32 Example......Page 64
6.3 In-Place Ordered (or Self-Sorting) Radix-2 FFT Algorithms......Page 67
7.1 Understanding Recursive DIT FFT & its In-Place Implementation......Page 68
7.2 Developing Iterative In-Place DIT FFT......Page 73
7.2.1 Identifying Twiddle Factors in DIT FFT......Page 75
7.3 Shorthand Notation & N = 32 Example......Page 76
Ch8 In-Place Radix-2 DIT FFT for Input in Bit-Reversed Order......Page 79
8.1 Developing Iterative In-Place DIT RN FFT......Page 84
8.1.1 Identifying Twiddle Factors in DIT RN FFT......Page 85
8.1.2 Pseudo-Code Program for DIT RN FFT......Page 87
8.2 Shorthand Notation & N =32 Example......Page 88
Ch9 Ordered Radix-2 DIT FFT......Page 90
9.1 Deriving (Ordered) DIT NN FFT from its Recursive Definition......Page 93
9.2 Pseudo-Code Program for DIT NN FFT......Page 96
9.3 Applying (Ordered) DIT NN FFT to N = 32 Example......Page 98
10.1 Bit-Reversal & Ordered FFTs......Page 101
10.2 Perfect Shuffle & In-Place FFTs......Page 102
10.2.1 Combining Software Implementation with FFT......Page 103
10.2.2 Data Adjacency Afforded by Hardware Implementation......Page 104
10.4 Fictitious Block Perfect Shuffle & Ordered FFTs......Page 105
10.4.1 Interpreting Ordered DIF NN FFT Algorithm......Page 106
10.4.2 Interpreting Ordered DIT NN FFT Algorithm......Page 107
11.1 Radix-4 DIT FFTs......Page 109
11.1.1 Analyzing Arithmetic Cost......Page 111
11.2 Radix-4 DIF FFTs......Page 113
11.3 Class of Radix-2s DIT & DIF FFTs......Page 116
12.2 Split-Radix DIT FFTs......Page 118
12.2.1 Analyzing Arithmetic Cost......Page 120
12.3 Split-Radix DIF FFTs......Page 121
12.4 Notes & References......Page 123
13.1 Main Ideas Behind Bluestein\'s FFT......Page 124
13.1.1 DFT & Symmetric Toeplitz Matrix-Vector Product......Page 125
13.1.2 Enlarging Toeplitz Matrix to Circulant Matrix......Page 127
13.1.3 Enlarging Dimension of Circulant Matrix to M = 2s......Page 129
13.1.4 Forming MXM Circulant Matrix-Vector Product......Page 130
13.1.5 Diagonalizing Circulant Matrix by DFT Matrix......Page 131
13.2 Bluestein\'s Algorithm for Arbitrary N......Page 133
14.1 Computing Two Real FFTs Simultaneously......Page 135
14.2 Computing Real FFT......Page 136
14.3 Notes & References......Page 138
Ch15 FFTs for Composite N......Page 139
15.1.1 Evaluating Polynomial by Nested-Multiplication......Page 140
15.1.2 Computing DFT by Nested-Multiplication......Page 141
15.2 2D Array as Basic Programming Tool......Page 142
15.2.1 Row-Oriented & Column-Oriented Code Templates......Page 143
15.3.1 Storing Vector in 2D Array......Page 144
15.3.2 Use of 2D Arrays in Computing DFT......Page 145
15.4 Efficient FFT for N = P X Q......Page 146
15.5.1 Storing 1D Array into Multi-Dimensional Array......Page 148
15.5.2 Row-Oriented Interpretation of v-D Arrays as 2D Arrays......Page 149
15.5.4 Row-Oriented Interpretation of v-D Arrays as 3D Arrays......Page 150
15.6 Programming Different v-D Arrays from Single Array......Page 151
15.6.1 Support from Fortran Programming Language......Page 152
15.6.2 Further Adaptation......Page 153
15.7 Efficient FFT for N = N0xN1x ··· xNv-1......Page 154
15.8 Notes & References......Page 158
16.1 Fast Polynomial Multiplication......Page 159
16.2 Fast Convolution & Deconvolution......Page 161
16.3 Computing Toeplitz Matrix-Vector Product......Page 163
16.4 Computing Circulant Matrix-Vector Product......Page 164
16.6 Fast Discrete Sine Transforms......Page 165
16.7 Fast Discrete Cosine Transform......Page 168
16.8 Fast Discrete Hartley Transform......Page 170
16.9 Fast Chebyshev Approximation......Page 172
16.10 Solving Difference Equations......Page 174
Part III Parallel FFT Algorithms......Page 180
Ch17 Parallelizing FFTs: Preliminaries on Data Mapping......Page 181
17.1 Mapping Data to Processors......Page 182
17.2 Properties of Cyclic Block Mappings......Page 183
17.3 Examples of CBM Mappings & Parallel FFTs......Page 185
Ch18 Computing & Communications on Distributed-Memory Multiprocessors......Page 187
18.1 Distributed-Memory Message-Passing Multiprocessors......Page 188
18.2 d-Dimensional Hypercube Multiprocessors......Page 189
18.2.1 Subcube-Doubling Communication Algorithm......Page 190
18.2.2 Modeling Arithmetic & Communication Cost......Page 191
18.2.3 Hardware Characteristics & Implications on Algorithm Design......Page 192
18.3 Embedding Ring by Reflected-Binary Gray-Code......Page 194
18.4 Further Twist--Performing Subcube-Doubling Communications on Ring Embedded in Hypercube......Page 196
18.5.2 Unidirectional Times on Circuit-Switched Networks......Page 198
18.5.3 Bidirectional Times on Full-Duplex Channels......Page 199
19.1 Useful Equivalent Notation: |PID | Local M......Page 201
19.1.1 Representing Data Mappings for Different Orderings......Page 204
19.2.1 Parallel DIF NR & DIT NR Algorithms......Page 207
19.2.4 Interpreting Data Mapping for Bit-Reversed Input......Page 213
19.4 Uneven Distribution of Arithmetic Workload......Page 214
20.1.1 Idea & Modified Shorthand Notation......Page 215
20.1.2 Complete Algorithm & Output Interpretation......Page 219
20.2 Improved Parallel DIF RN & DIT RN Algorithms......Page 224
20.3 Further Technical Details & Generalization......Page 225
Ch21 Potpourri of Variations on Parallel FFTs......Page 227
21.1.1 PID in Gray Code......Page 228
21.1.2 Using Ordered FFT on Local Data......Page 229
21.1.4 FFTs for Connection Machines......Page 230
21.2.2 Pivoting on Right-Most Bit in Local M......Page 232
21.2.3 All-to-All Inter-Processor Communications......Page 233
21.2.4 Maintaining Specific Maps for Input & Output......Page 234
21.4 Notes & References......Page 237
22.1.1 Algorithm I......Page 239
22.1.2 Algorithm II......Page 240
22.2.1 Phase I of General Algorithm......Page 242
22.2.2 Phase II of General Algorithm......Page 244
23.1 Computation of Multiple 1D FFTs......Page 247
23.2 Sequential 2D FFT Algorithm......Page 248
23.2.2 Computing Single 1D FFT Stored in 2D Matrix......Page 249
23.2.3 Sequential Algorithms for Matrix Transposition......Page 250
23.3.1 Transpose Split (TS) Method......Page 252
23.3.2 Local Distributed (LD) Method......Page 253
23.3.4 Transforming Rectangular Signal Matrix on Hypercubes......Page 254
23.4 Generalized 2D Block Distributed (GBLK) Method for Subcube-Grids & Meshes......Page 255
23.4.1 Running Hypercube (Subcube-Grid) Programs on Meshes......Page 256
23.5.1 Minimizing Multi-Hop Penalty......Page 257
23.5.2 Minimizing Traffic Congestion......Page 258
23.6 Pipelining Subcube-Doubling Communications on all Hypercube Channels......Page 262
23.8 Parallel Matrix Transposition by Changing Data Mapping......Page 269
23.9 Notes & References......Page 271
Ch24 Computing & Distributing Twiddle Factors in Parallel FFTs......Page 274
24.1 Twiddle Factors for Parallel FFT without InterProcessor Permutations......Page 275
24.2 Twiddle Factors for Parallel FFT with InterProcessor Permutations......Page 280
Part IV Appendices......Page 281
A1.1 Relating Operation Counts to Execution Times......Page 282
A1.2 Relating MFLOPS to Execution Times & Operation Counts......Page 283
A2.1 Informal Introduction via Motivating Examples......Page 284
A2.2 Formal Notations & Terminologies......Page 285
A2.3 Big-O & Big-Omega Notations......Page 286
A2.4 Some Common Uses of Q-Notation......Page 287
B2 Solving Recurrences to Determine Unknown Function......Page 288
B3 Mathematical Summation Formulas......Page 291
B4 Solving Generalized Recurrence Equations......Page 293
B5 Recurrences & FFT......Page 299
Bibliography......Page 301