Barnes-Hut simulation

The Barnes-Hut simulation, named after Joshua Barnes and Piet Hut, is an approximation algorithm for n-body simulation. A direct sum over every pair of bodies costs on the order of n squared, while this method has order n log n. It divides the simulated volume into cells with an octree, or a quadtree in two dimensions, and stores the total mass and center of mass in each internal node. To find the force on one body, the tree is walked from the root: a cell that is far enough away, judged by the ratio of its width to its distance compared with a threshold theta, is treated as one large particle, and a nearer cell is opened into its children. Larger theta values are faster but less accurate, and theta of zero reduces to the direct sum. It is used in computational astrophysics treecodes.