Fast Multipole Method—an algorithm for GPUs and exascale computing

<b>Invited Lecture at the SIAM <i>"Encuentro Nacional de Ingeniería Matemática,"</i> at Pontificia Universidad Católica de Chile, Santiago, August 2015.</b><div><br></div><div>The fast multipole method is 30 years old: one of its inventors (Leslie Greengard) published his MIT doctoral thesis in 1985. The journal paper "A fast algorithm for particle simulations” (1987) has amassed more than 4,000 citations by now, and the algorithm was chosen as one of the Top-10 of the 20th century. In the last 5 years or so, the FMM has become an even hotter topic, and we argue that there are three reasons. (1) as computers have gotten faster, these algorithms have become more competitive; (2) they scale well in parallel and can exploit many-core GPU hardware; and (3) they can do much more than solve N-body problems. We will review the basic features of these algorithms and explain why they have become more popular recently. To quantify the advantages of N-body algorithms on GPU hardware, we will rely on the "roofline model,” a useful tool to analyze computational kernels and identify performance limitations on specific hardware. Recently, there have been several developments in the computer-science aspects of implementing the FMM with high performance, as well as in the applications arena. We will discuss the most recent advances and give perspectives for the future of exascale computing.