The N-body problem is a classic problem involving a system of N discrete bodies mutually interacting in a dynamical system. At any moment in time there are N(N−1)/2 such interactions occurring. This N2 scaling leads to computational difficulties where simulations range from tens of thousands of bodies to billions or trillions. Approximation algorithms, such as the famous Barnes–Hut algorithm, simplify the number of interactions to scale as NlogN. Even still, this improvement in complexity is insufficient to achieve the desired performance for very large simulations on computing clusters with many nodes and many cores. In this work we explore a variety of algorithmic techniques for parallel and distributed variations on the Barnes–Hut algorithm to improve parallelism and reduce inter-process communication requirements. This includes the costzones and hashed octree techniques. We implement these techniques in a gravitational N-body simulation and show that they can be applied to both a parallel and distributed context. This work collects and unifies over 30 years of research, while filling in missing details, to provide a comprehensive and reproducible source.
Alexander Brandt (2026) studied this question.