Self-Gravity is a key phenomena in many Astrophysical Simulations, hence the solution of Poisson's equation of the gravitational potential Φ(x) for a given density distribution ρ(x)

is one of the main functions in these simulations. The direct method for evaluating the gravitational potential at position xi of a point mass mi requires the evaluation of all pairwise interactions in the system.

where, mj is the mass of the jth particle and ri and rj are the position vectors of particle i and j. While the direct method with it's O(N2) arithmetic complexity is conceptually simple, it is obviously unsuitable for larger systems. Luckily several heuristic algorithms are available which require fewer operations within acceptable error bounds.

The Barnes & Hut tree algorithm

The Barnes & Hut tree algorithm for three-dimensions works by grouping 'particles' or 'grid-cells' using an octree structure. In FLASH4, the domain decomposition is carried out with the PARAMESH library. Our code implements an own iterative octree building on the GPU device.

For each tree node, the total mass and the center of mass is calculated. The force on a particle in the system is evaluated by "walking" down the tree. At each level, every node is tested against a test particle if it is distant enough for a force evaluation. If the node is too close, it is "opened" and the 8 children are selected for the same procedure. Various criteria exist to test whether a particle is sufficiently distant for a force evaluation. Here, we adopt the opening angle parameter described by Barnes & Hut(1994) with

where δ is the distance between the center of mass of the node and the geometric center. This criterion guarantees that if the center of mass is near the node's edge, only positions removed by an extra distance δ use the data cell for a force evaluation.