| We start by motivating the FFT (Fast Fourier Transform) as a solver for Poisson's equation |
| The we discuss sequential 1D discrete FFT in both DIF (Decimation in Frequency) and DIT (Decimation in Time) modes |
| We describe general N=N1*N2 case but soon specialize to binary (Cooley Tukey) FFT. |
| For binary case, we go through parallelism and use of cache giving a performance analysis |
| These lectures motivate later lectures on Fast Multipole method as general Green's function solver which is more flexible than FFT |
001 Parallel FFT and Use in PDE Solvers 002 Abstract of CPS615 FFT Lectures 003 References for Fast Fourier Transform 004 Solving Poisson's Equation with the FFT I 005 Solving Poisson's Equation with the FFT II 006 Discrete Fourier Transform 007 Inverse and other FFT Transforms 008 The 1D FFT in explicit detail I 009 The 1D FFT in explicit detail II 010 DIF Manipulation of the exponential I 011 DIF Manipulation of the exponential II 012 Recursive Formula for DIF 013 The Computational Complexity of DIF FFT 014 DIT Manipulation of the exponential I 015 DIT Manipulation of the exponential II 016 Recursive Formula for DIT 017 Recursive Structure for DIT 018 What's Going On with DIT/DIF I 019 What's Going On with DIT/DIF II 020 What's Going On with DIT/DIF III 021 Butterfly Pattern in 1D DIT FFT 022 Basic Parallel FFT Algorithms I 023 Basic Parallel FFT Algorithms II 024 Parallelism in 1D FFT 025 Performance of Simplest Parallel DIT FFT I 026 Performance of Simplest Parallel DIT FFT II 027 Performance of Simplest Parallel DIT FFT III 028 Performance of Simplest Parallel DIT FFT IV 029 Performance of Simplest Parallel DIT FFT V 030 What's Going On with DIT/DIF IV 031 Sequential and Parallel Performance I 032 Sequential and Parallel Performance II 033 Sequential and Parallel Performance III 034 Sequential and Parallel Performance IV 035 Sequential and Parallel Performance V 036 Parallel FFT and Hypercubes I 037 Parallel FFT and Hypercubes II 038 Multi Dimensional FFT's