2026/04/22 by Alexander Brandt · 1 voice
Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Scientific Research and Discoveries #Stellar, planetary, and galactic studies
paper · doi:10.3390/math14091403
openalex publication_date 2026/04/22 · openalex created_date 2026/04/23 · openalex updated_date 2026/07/23
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.