FFT, FMM, OR MULTIGRID? A COMPARATIVE STUDY OF STATE-OF-THE-ART POISSON SOLVERS

Abstract. We discuss the fast solution of the Poisson problem on a unit cube. We benchmark the performance of the most scalable methods for the Poisson problem: the Fast Fourier Transform (FFT), the Fast Multipole Method (FMM), the geometric multigrid (GMG) and algebraic multigrid (AMG). The GMG and FMM are novel parallel schemes using high-order approximation for Poisson problems developed in our group. The FFT code is from P3DFFT library and AMG code from ML Trilinos library. We examine and report results for weak scaling, strong scaling, and time to solution for uniform and highly refined grids. We present results on the Stampede system at the Texas Advanced Computing Center and on the Titan system at the Oak Ridge National Laboratory. In our largest test case, we solved a problem with 600 billion unknowns on 229,379 cores of Titan. Overall, all methods scale quite well to these problem sizes. We have tested all of the methods with different source distributions. Our results show that FFT is the method of choice for smooth source functions that can be resolved with a uniform mesh. However, it loses its performance in the presence of highly localized features in the source function. FMM and GMG considerably outperform FFT for those cases