Foilset Search Full Index for Basic foilset

Parallel FFT and use in PDE Solvers

Given by Geoffrey C. Fox at Computational Science Class CPS615 on Winter Semester 2000. Foils prepared April 22 2000

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

Table of Contents for Parallel FFT and use in PDE Solvers

There are two types of foils -- html and image which are each available in basic and JavaScript enabled "focused" style
(basic:)(focus style:) Denote Foils where Image Critical
(basic:)(focus style:) Denote Foils where HTML is sufficient
1 Parallel FFT and Use in PDE Solvers
2 Abstract of CPS615 FFT Lectures
3 References for Fast Fourier Transform
4 Solving Poisson's Equation with the FFT I
5 Solving Poisson's Equation with the FFT II
6 Discrete Fourier Transform
7 Inverse and other FFT Transforms
8 The 1D FFT in explicit detail I
9 The 1D FFT in explicit detail II
10 DIF Manipulation of the exponential I
11 DIF Manipulation of the exponential II
12 Recursive Formula for DIF
13 The Computational Complexity of DIF FFT
14 DIT Manipulation of the exponential I
15 DIT Manipulation of the exponential II
16 Recursive Formula for DIT
17 Recursive Structure for DIT
18 What's Going On with DIT/DIF I
19 What's Going On with DIT/DIF II
20 What's Going On with DIT/DIF III
21 Butterfly Pattern in 1D DIT FFT
22 Basic Parallel FFT Algorithms I
23 Basic Parallel FFT Algorithms II
24 Parallelism in 1D FFT
25 Performance of Simplest Parallel DIT FFT I
26 Performance of Simplest Parallel DIT FFT II
27 Performance of Simplest Parallel DIT FFT III
28 Performance of Simplest Parallel DIT FFT IV
29 Performance of Simplest Parallel DIT FFT V
30 What's Going On with DIT/DIF IV
31 Sequential and Parallel Performance I
32 Sequential and Parallel Performance II
33 Sequential and Parallel Performance III
34 Sequential and Parallel Performance IV
35 Sequential and Parallel Performance V
36 Parallel FFT and Hypercubes I
37 Parallel FFT and Hypercubes II
38 Multi Dimensional FFT's
Full WebWisdom URL and this Foilset Search
This contains all WebWisdom links preceded by those referenced in this foilset
© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Mon Apr 24 2000