Fast multipole method

The fast multipole method (FMM) was invented as an algorithm to calculate a gravitational $N$-body problem efficiently. The interaction of $N$ masses appears to be a very expensive computation: its complexity is $O(N^2)$ because all bodies affect the gravitational potential at any one point. But with the knowledge that the force of gravitation decays with distance, we can use series expansions to approximate many masses that are far enough away. This is a very powerful idea that has found wide applications in science. In fact, the FMM has been chosen as one of the Top 10 Algorithms of the 20th Century.

The integral formulation of problems modelled by elliptic partial differential equations (PDEs) leads to numerical integration. Computationally, this has the same form as an $N$-body interaction, and the FMM can be used to obtain a result in $O(N)$ operations. In this way, fast $N$-body algorithms find application in acoustics, eletromagnetics, and fluid dynamics.

Applications of the fast multipole method

Fast multipole method on GPU hardware

The FMM accelerates $N$-body calculations from $O(N^2)$ to $O(N)$, but this algorithmic speed-up is multiplied by the hardware speed-up obtained when using GPU hardware.

In November 2011, we released the exaFMM code under the MIT license. This code is written in C++, is accelerated on GPUs with CUDA, and is parallel with MPI. We were able to run tests on a large GPU system, thanks to guest access via the Grand Challenge program of Tsubame in Japan, achieving 1 petaflop/s on a turbulence calculation using 4096 GPU cards.

References

• "ExaFMM: An open source library for Fast Multipole Methods aimed towards Exascale systems", L. A. Barba, Rio Yokota. (31 May 2012). 10.6084/m9.figshare.92166
  

  Poster, published on figshare under CC-BY

• "ExaFMM: An open source library for Fast Multipole Methods", L. A. Barba, Rio Yokota. (18 June 2012). 10.6084/m9.figshare.92426
  

  Trifold brochure, distributed with the exaFMM poster, published on figshare under CC-BY

• "Weak scaling of parallel FMM vs. FFT up to 4096 processes", Rio Yokota, L. A. Barba. (18 June 2012). 10.6084/m9.figshare.92425 // exaFMM webpage
  

  Figure, data and plotting script published on figshare under CC-BY

• "Petascale turbulence simulation using a highly parallel fast multipole method", Rio Yokota, L. A. Barba, Tetsu Narumi, Kenji Yasuoka. Comput. Phys. Comm., 184(3):445–455 (March 2013). 10.1016/j.cpc.2012.09.011 // Preprint arXiv:1106.5273 // exaFMM code webpage
  

  Published online 13 Sept. 2012.

Talk: July 2020

ExaFMM - 10+ years, 7 re-writes. The tortuous progress of computational research