Multipole is an
This matters most for dynamics. Realistic simulations typically need thousands to millions of time steps, and the force calculation is repeated at every step. Linear scaling therefore reduces total runtime by orders of magnitude, making long-timescale, large-scale many-body simulations feasible.
- Algorithmic overview
- The two-phase hierarchical process
- Final force and potential evaluation
- Accuracy and cost
- Build and run
- References
The algorithm splits the potential at each particle into two physical regimes:
| Regime | Source particles | Method |
|---|---|---|
| Near field | Particles in the same cube or in adjacent cubes | Direct pairwise summation |
| Far field | All other particles | Compact series expansions (multipole and local) |
The far-field series converge geometrically for well-separated sources. To reach a target precision
The far field is evaluated in
The upward pass builds a multipole expansion for every cube in the tree, from the finest level up to the root.
- Leaf initialization. At the finest level of refinement, the field of each particle is expanded about the center of its leaf cube, and the contributions are summed into a single multipole expansion per leaf.
- Tree propagation (M2M). Moving up one level at a time, the expansions of a node's eight children are shifted to the parent's center (a multipole-to-multipole translation) and summed.
- Validity. At the end of this phase, every node at every level holds a multipole expansion of the field produced by all particles inside it. Each expansion is valid only outside the cube's near-field region.
The downward pass builds a local (Taylor) expansion for every cube, starting at the coarsest level.
- Root initialization. The root has no parent and no interaction list, so its local expansion is initialized to zero.
-
Multipole-to-local translation (M2L). For each cube, the multipole expansions of every cube in its interaction list are converted to local expansions about the cube's center and summed. The interaction list consists of the children of the parent's neighbors that are not themselves neighbors of the cube. In three dimensions it contains at most
$6^3 - 3^3 = 189$ cubes. - Local-to-local translation (L2L). The parent's local expansion is shifted to the center of each child cube and added to the contribution from the child's interaction list.
- Propagation. Repeating this down the tree means that, at every level, a cube's local expansion represents the field of all particles outside the cube and its immediate neighbors.
For each leaf cube
-
Far-field component. The cube's local expansion, a
$p$ -term Taylor series, is evaluated directly at each particle position. This gives the contribution of all distant particles. -
Near-field component. Interactions between each particle in cube
$i$ and the particles in the cube itself and its neighbors are computed by direct summation.
The total potential is their sum:
The result is exact up to the truncation error set by
-
Linear scaling. The number of cubes is proportional to
$N$ when the tree depth is chosen so each leaf holds a roughly constant number of particles. Each cube then requires a bounded number of translations (at most 189 M2L operations, one L2L, and eight M2M contributions), so total cost grows as$O(N)$ . -
Accuracy versus speed. Raising
$p$ lowers the far-field error geometrically but increases the cost of every translation. Choose the smallest$p$ that meets your required precision. - Tree depth. Deeper trees shrink the near-field (direct) work and grow the far-field work. The best depth balances the two.
Compile and run the program from a terminal:
./configure
make
./multipoleThe hierarchical multipole algorithm is described in detail in these technical reports:
"Computational Simulation of Multi-Body Interactions with O(N) Scaling" Cristy and David A. Pensak, Central Research and Development, E. I. du Pont de Nemours and Company, Technical Report, June 1991.
"An O(N) Algorithm for Three-dimensional N-body Simulations" Feng Zhao, MIT Artificial Intelligence Laboratory, Technical Report 995, 1987.
Note: The formula for the lexicographic ordering of the tetrahedral array used in this framework was derived by Richard Merrifield.
