Journal Article

A fast recursive coordinate bisection tree for neighbour search and gravity

Emanuel Gafton and Stephan Rosswog

in Monthly Notices of the Royal Astronomical Society

Published on behalf of The Royal Astronomical Society

Volume 418, issue 2, pages 770-781
Published in print December 2011 | ISSN: 0035-8711
Published online November 2011 | e-ISSN: 1365-2966 | DOI:
A fast recursive coordinate bisection tree for neighbour search and gravity

More Like This

Show all results sharing this subject:

  • Astronomy and Astrophysics


Show Summary Details


We introduce our new binary tree code for neighbour search and gravitational force calculations in an N-particle system. The tree is built in a ‘top-down’ fashion by ‘recursive coordinate bisection’ where on each tree level we split the longest side of a cell through its centre of mass. This procedure continues until the average number of particles in the lowest tree level drops below a prescribed value. To calculate the forces on the particles in each lowest-level cell we split the gravitational interaction into a near- and a far-field. Since our main intended applications are smoothed particle hydrodynamic (SPH) simulations, we calculate the near-field by a direct, kernel-smoothed summation, while the far field is evaluated via a Cartesian Taylor expansion up to quadrupole order. Instead of applying the far-field approach for each particle separately, we use another Taylor expansion around the centre of mass of each lowest-level cell to determine the forces at the particle positions. Due to this ‘cell–cell interaction’ the code performance is close to where N is the number of used particles. We describe in detail various technicalities that ensure a low memory footprint and an efficient cache use.

In a set of benchmark tests we scrutinize our new tree and compare it to the ‘Press tree’ that we have previously made ample use of. At a slightly higher force accuracy than the Press tree, our tree turns out to be substantially faster and increasingly more so for larger particle numbers. For four million particles our tree build is faster by a factor of 25 and the time for neighbour search and gravity is reduced by more than a factor of 6. In single processor tests with up to 108 particles we confirm experimentally that the scaling behaviour is close to . The current Fortran 90 code version is OpenMP-parallel and scales excellently with the processor number (=24) of our test machine.

Keywords: gravitation; hydrodynamics; methods: numerical

Journal Article.  10176 words.  Illustrated.

Subjects: Astronomy and Astrophysics

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.