Fast multipole methods for multiparticle simulations

Abstract

The fast multipole method (FMM) reduces the computation cost of the pairwise non-oscillating interaction between N particles from O(N^2) to O(N). In the FMM, the contribution from a source particle is represented as a multipole expansion, while the contributions from multiple faraway sources can be combined into a local expansion around an objective particle. Without the dependence on a grid covering the whole domain under study, the FMM treats any charge distribution and geometry in a natural way. It avoids artificial smoothing due to the grid size and redundant computation on the free space grids. We will introduce the concept of the FMM using the Coulomb interaction as an example and then explain how the FMM can be extended to arbitrary non-oscillating interactions. Examples and discussions on how the FMM can be used in scientific simulations, especially in accelerator physics will also be provided.