FFTs and three-dimensional Poisson solvers for hypercubes (Q1175197)

In many applications, very much fast Fourier transforms (FFTs) need to be computed. An important example is provided by various fast Poisson solvers. In particular, Poisson's equation on a cube can be solved by using Fourier transforms in two directions and tridiagonal linear equation solvers for the third coordinate. This paper is a careful study of the performance of various strategies to parallelize these algorithms on hypercubes. A number of alternatives for the FFT are introduced and formulas for their running time are developed and compared with actual performance on an Intel system. A similar study is then conducted for fast Poisson solvers. The paper ends with a discussion of two additional Poisson solvers, which had not been tested by the time of the completion of this project.