Abstract of CPS615 FFT Lectures
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