Lorena A. Barba group

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

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.


Talk: July 2020

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