Fast Multipole Method

Olga Abramova, Yulia Itkulova, Dmitry Maryin, Victor Malyshev, Elena Moiseeva, Nail Gumerov

Most of the problems studied in the laboratory are united by the basic algorithm, the fast multipole method (FMM).

The FMM was originally developed by American scientists Rokhlin and Greengard in 1987 and it was intended for fast computation of the N-body problem. According to experts the FMM along with such algorithms as the fast Fourier transform (FFT) entered the top ten best algorithms of the 20th century. It is known that the exact computation of the interaction potential for N-body requires N2 operations. The proposed algorithm solves this problem using only kN operations, where k is much less than N. For a large N it allows accelerating of calculations orders of magnitude, and solving problems that simply could not be solved using a standard algorithm. The difference between the FMM and another revolutionary algorithm, the FFT, is that the FFT requires that all the data points are located on a uniform grid, which is certainly not the case for problems that includes stars or atoms, while the FMM may be used for arbitrary (unstructured) data sets.

The hierarchical structure of the Fast Multipole Method

The FMM achieves its goal by using complex hierarchical (adaptive) data structure and mathematical theory of expansion and translation of functions. This makes the FMM a relatively difficult both for understanding and for efficient implementation, especially on data-parallel processors. Over the past two decades the scientists from the U.S., Europe, Japan, and other countries demonstrated impressive results in computation of fluid flows, acoustics, electromagnetism, molecular dynamics, etc. obtained using the FMM. However in Russia the FMM has not received proper development and popularity and its active use started only recently. 

Universality of the method is due to the fact that classical linear and nonlinear problems can be reduced to solution of large, dense systems of equations, which is the main computational problem (for example, it can consume up to 99% of all computing resources) and the acceleration of solutions is of great importance. The FMM splits the matrix vector product into sparse and dense parts which can be computed independently and in parallel. The sparse part is computed directly, while the dense part is computed approximately with a required accuracy (using expansions). The scale of modern problems solved by direct modeling based on the "first" principles (the computation of the pairwise interaction forces in systems with millions of molecules or solution of the Navier-Stokes equations in domains with complex boundaries due to highly discretized boundaries of channels and particles of arbitrary shape) is such that it makes FMM-like methods particularly significant. Combination of low complexity and a high degree of parallelism makes the FMM an attractive method for the Peta-scale and Exa-scale computing era.

The run time of one time step of simulation of dynamics of water molecules using straightforward technique (brute force) and using FMM, with and without utilization of graphic processing units (GPU)

Despite a short time since its foundation, the laboratory became a pioneer and leader in the FMM in Russia. The FMM course developed at the Institute for Advanced Computer Studies at the University of Maryland (USA) was taught to the laboratory researchers. Pioneering studies include the FMM implementation for direct calculation of the Stokesian dynamics of deformable droplets. Here the solutions were obtained for systems with more than ten thousand droplets (the problem, where at each time step a solution of a dense algebraic system with more than one million unknowns is required). The FMM is also used for fast calculations of the electrostatic potential in systems with a large number of polar molecules. Currently the application of the FMM for direct calculation of bubbles self-organization in acoustic fields is under development. In addition, the laboratory conducts research on the implementation of parallel version of the FMM on heterogeneous architectures, which contain several central and graphics processors. The first results in this direction are very impressive and are already implemented in software packages simulating the dynamics of emulsions and molecular dynamics. The results were reported on Russian conferences as well as on International conferences including the ICNMMF (International Conference on Numerical Methods in Mechanics of Multiphase Flows, Pennsylvania, USA, June 12-14, 2012) and the ASME IMECE'2012 (Congress of American Society of Mechanical Engineers, Texas, USA, November 9-15, 2012).