multipolmetod

The multipole method, sometimes rendered as multipolmetod in certain languages, is a class of numerical algorithms designed to efficiently compute long-range interactions in systems with many particles. Instead of calculating every pairwise interaction, the method approximates the collective effect of groups of distant sources using mathematical multipole expansions, reducing the overall computational effort.

The approach relies on a hierarchical decomposition of space, typically using trees (quad-trees in two dimensions, octrees in three dimensions). An upward pass computes multipole coefficients for small cells and propagates them up the tree. A translation phase converts distant cell multipoles into local expansions for target regions, enabling fast evaluation of their influence. A downward pass then distributes these local fields toward finer cells, while near-field interactions are evaluated directly to maintain accuracy. Key components include M2M (multipole-to-multipole), M2L (multipole-to-local), and L2L (local-to-local) translation operators, along with local expansions for efficient evaluation.

The fast multipole method (FMM) is the most widely known realization of this idea, introduced by Greengard and Rokhlin, and it achieves near-linear or linear-time complexity under suitable conditions. Related approaches, such as the Barnes–Hut tree algorithm, provide alternative trade-offs between accuracy and performance. Variants of the multipole method extend to different physical kernels (gravity, electrostatics, acoustics), boundary conditions, and adaptive discretizations.

Applications span physics and engineering, including N-body simulations in astrophysics, molecular dynamics, and electrostatic computations in chemistry. Limitations include algorithmic complexity, implementation overhead, and performance sensitivity to particle distribution and expansion order.