Parallel three-dimensional nonequispaced Fast Fourier Transforms and their application to particle simulation

Abstract. In this paper we describe a parallel algorithm for calculating nonequispaced fast Fourier transforms on massively parallel distributed memory architectures. These algorithms are implemented in an open source software library called PNFFT. Furthermore, we derive a parallel fast algorithm for the computation of the Coulomb potentials and forces in a charged particle system, which is based on the parallel nonequispaced fast Fourier transform. To prove the high scalability of our algorithms we provide performance results on a BlueGene/P system using up to 65536 cores. Key words and phrases: parallel nonequispaced fast Fourier transform, parallel fast summation, parallel particle mesh methods, NFF