by Ben Prather

# The Barnes-Hut Algorithm

The Barnes-Hut algorithm approximately solves the N-body problem using only O(N log(N)) time

## Presentation Summary

In this presentation, I give an overview of the Barnes-Hut algorithm, an optimization of the usual solution to the N-body problem at the cost of some accuracy. It works by approximating far-away clusters of objects as single, larger objects.

## References

- Original Paper: Barnes & Hut, “A hierarchical O(N log N) force-calculation algorithm,” Nature 324, 446 - 449 (04 December 1986); doi:10.1038/324446a0
- Parallel examples: Scala, Other
- Gravitational interaction speed
- Notable N-body simulations: Bolshoi, Millennium
- Björk concert: “Dark Matter,” Bestival 2011

Yubo "Paul" Yang ALGORITHM

n-body astrophysics