A talk presented to the Theory of Condensed Matter Electronic Structure Discussion Group on Wednesday 7 November 2001.

This talk is based largely on the paper:

Parallel fast Fourier transforms for electronic structure calculations, Peter D. Haynes and Michel Côté, *Comput. Phys. Commun.* **130**, 130 (2000)

The overheads are available in the following formats:

- HTML (below)
- Compressed (gzipped) PostScript
- Portable Document Format (viewable with Adobe's Acrobat Reader)

- Contents:
- Motivation
- Fourier series
- Discrete Fourier transforms
- Slow Fourier Transforms
- Danielson-Lanczos Lemma
- Fast Fourier Transforms
- 3D Fourier Transforms
- Traditional Parallel Fast Fourier Transforms
- New Parallel Fast Fourier Transforms
- Alternative Distribution
- Cost comparison
- Cost modelling
- Cost for traditional method
- Cost for new method
- Results
- Load balancing
- Application to
*O(N)*methods - Subcells
- FFT box
- Advantages of the new FFT method

- About this document ...

Peter D. Haynes 2001-11-07