PVFMM: A Parallel Kernel Independent FMM for Particle and Volume Potentials (Communications in Computational Physics, 2018)
We describe our implementation of a parallel fast multipole method for evaluatingpotentials for discrete and continuous source distributions. The first requiressummation over the source points and the second requiring integration over a continuoussource density. Both problems require $\mathcal{O}$($N^2$) complexity when computed directly;however, can be accelerated to $\mathcal{O}$($N$) time using FMM. In our PVFMM softwarelibrary, we use kernel independent FMM and this allows us to compute potentials fora wide range of elliptic kernels. Our method is high order, adaptive and scalable. Inthis paper, we discuss several algorithmic improvements and performance optimizationsincluding cache locality, vectorization, shared memory parallelism and use ofcoprocessors. Our distributed memory implementation uses space-filling curve forpartitioning data and a hypercube communication scheme. We present convergenceresults for Laplace, Stokes and Helmholtz (low wavenumber) kernels for both particleand volume FMM. We measure efficiency of our method in terms of CPU cycles perunknown for different accuracies and different kernels. We also demonstrate scalabilityof our implementation up to several thousand processor cores on the Stampedeplatform at the Texas Advanced Computing Center.