A Hierarchical O(N) Force Calculation Algorithm

By W. Dehnen. 2002

327 citations recorded by the source corpus.

A novel code for the approximate computation of long-range forces between N mutually interacting bodies is presented. The code is based on a hierarchical tree of cubic cells and features mutual cell–cell interactions which are calculated via a Cartesian Taylor expansion in a symmetric way, such that total momentum is conserved. The code benefits from an improved and simple multipole acceptance criterion that reduces the force error and the computational effort. For N≳104, the computational costs are found empirically to rise sublinearly with N. For applications in stellar dynamics, this is the first competitive code with complexity O(N); it is faster than the standard tree code by a factor of 10 or more.

Subfields: Atomic and Molecular Physics, and Optics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/c58bc2d1b4e566f332ae0bdf48de12a7702ca72c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Statistical and Nonlinear Physics

Citations in the corpus

On the nature of bulges in general and of box/peanut bulges in particular: input from N-body simulations (2005, methodology): “They were run either on our GRAPE5 systems (Kawai et al. 2000) or with a tree-code on a PC (Dehnen 2000, 2002).”
THE NUCLEUS OF THE SAGITTARIUS DSPH GALAXY AND M54: A WINDOW ON THE PROCESS OF GALAXY NUCLEATION (2008, methodology): “General features of the N-body experiments The simulations were performed with falcON, a fast and momentum-conserving tree-code (Dehnen 2000, 2002), within the NEMO environment (Teuben 1995).”
Galaxy merging, the fundamental plane of elliptical galaxies and the MBH-σ0 relation (2003, methodology): “Recently, a numerical scheme has been introduced to simulate collisionless N-body systems by Dehnen (2000, 2002), with a substantial improvement in force computation over standard tree–based codes.”
Linear-time Algorithms for Pairwise Statistical Problems (2009, methodology): “A hierarchical data structure was also developed for efficient combined potential calculation in computational physics in Barnes & Hut, 1986 [5].”
A comparison of domain integral evaluation techniques for boundary element methods (2001, methodology): “However, in the present approach using the Barnes–Hut algorithm [23] for the evaluation of the domain integral, the operation count per collocation node is reduced from O(M) for classical Gaussian quadrature to O(logM) for multipole evaluation.”
ARGOS – IV. The kinematics of the Milky Way bulge (2013, methodology): “Theirevolution was followed using the Gyrfalcon N-body code (Dehnen 2000, 2002).”
What determines the strength and the slowdown rate of bars (2003, methodology): “…made with the Marseille Grape-5 computers (for a description of Grape-5 boards and their performance see Kawai et al. 2000), using a tree-code specifically adapted to this hardware, while roughly 20% of the simulations were run with W. Dehnen’s treecode on PC workstations (Dehnen 2000, 2002).”
Astrophysical smooth particle hydrodynamics (2009, methodology): “Dehnen (2000, 2002) has used ideas from the Fast Multipole Method (FMM) (Greengard and Rokhlin, 1987) for a fast tree code which scales proportional to OðNÞ.”
Quantifying the heart of darkness with GHALO – a multibillion particle simulation of a galactic halo (2008, methodology): “PKDGRAV2 uses a fast multipole method (FMM) similar to Dehnen (2000, 2002) but using a 5th-order reduced expansion for faster and more accurate force calculation in parallel, and a multipole based Ewald summation technique for periodic boundary conditions (Stadel 2001).”