|
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
|
