Barnes-Hut Algorithm

The Barnes-Hut Algorithm¹ is an approximation algorithm solving the N-Body Problem.

It is notable for having order O(N log N) compared to a direct sum - Brute Force - algorithm which would be O(N^2). The crucial idea is that it groups nearby bodies and approximates them as a single body. If the cluster is sufficiently far away, we can approximate its gravitational effect using its center of mass.

Quickstart

• In order to run this in your local machine:

> git clone https://github.com/alessialin/BarnesHut-py.git
> cd BarnesHut-py
> pip install -r requirements.txt

NB. I'd suggest setting up a virtual environment beforehand to avoid polluting your machine's modules system.

• To run the Barnes-Hut simulation:

> python3 ./src/BarnesHut-py.py

Files Structure

├── evaluation
│   └── BarnesHut_evaluation.py
|   └── BruteForce_evaluation.py
│   └── comparison.py
├── output
│   └── benchmark
|   │   └── BarnesHut_time.png
|   │   └── BruteForce_time.png
|   │   └── Comparison_time.png
│   └── BH_GalaxyCollision_800_v[x].mp4
│   └── BH_GalaxySimulation_800_v[x].mp4
│   └── BH_Quad.png
├── src
|   └── BarnesHut.py
|   └── body.py
│   └── node.py
│   └── quadtree_example.py
│   └── quadtree.py
│   └── utils.py
├── .gitignore
├── LICENSE
├── README.md
└── requirements.txt

Simulation

BH_GalaxyCollision_800_v0.mp4

Resources

Barnes, J., & Hut, P. (1986). A hierarchical O (N log N) force-calculation algorithm. Nature, 324(6096), 446-449.
Wikipedia
Galaxy Simulator
Princeton CS126
The Barnes-Hut Approximation

Footnotes

1. The purpose of this repository is for the final submission of the course of 20602 COMPUTER SCIENCE (ALGORITHMS) at Bocconi University. ↩