Parallel 3D Fast Fourier Transform

This video by Thomas Koopman and Rob Bisseling shows how to move from a sequential 1D FFT algorithm to a parallel 1D FFT algorithm to a parallel 3D FFT algorithm based on a cyclic distribution of the data. We discuss three different 3D distributions, namely slab, pencil, and cyclic and show that the cyclic distribution only needs a single data redistribution during the algorithm. Here, a good choice of notation makes the development of the parallel 3D FFT much easier. We present results of our software implementation FFTU, the Fastest Fourier Transform in Utrecht, which uses the package FFTW for its sequential part. We compare FFTU with three other packages, PFFT, FFTW, and heFFTe and we show that FFTU achieves state-of-the-art performance. This video corresponds to the article "Minimizing communication in the multidimensional FFT", by Thomas Koopman and Rob H. Bisseling, SIAM Journal on Scientific Computing, Volume 45, Number 6 (2023) pp. C330-C347. It is the first video in the series "Beyond the book", and it represents our own attempt to answer Exercise 3.5 of the book Parallel Scientific Computation: A Structured Approach Using BSP, Second Edition, by Rob H. Bisseling, Oxford University Press, 2020. The FFTU software accompanying the paper can be found at https://gitlab.com/Thomas637/FFT The paper can be found at https://doi.org/10.1137/22M1487242