A hierarchical O(N log N) force-calculation algorithm

By J. Barnes, P. Hut. 1986

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “…constructs a knearest neighbor graph over the high dimensional space to record local neighborhood structure, and utilizes the Barnes-Hut force calculation algorithm (which is typically used for multi-body simulation; Barnes and Hut, 1986) to accelerate optimization of the low-dimensional embedding.”
Fast Interpolation-based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data (2017, methodology): “t change, they can be precomputed, and hence do not dominate the computational time. On the other hand, the repulsive forces F rep;i are approximated at each iteration using the Barnes-Hut Algorithm (Barnes and Hut (1986)), a tree-based algorithm which scales as O(nlogn). Despite these accelerations”
ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software (2014, methodology): “In order to improve spatialization performances on big graphs, we implemented the optimization of Barnes Hut [20].”
Barnes-Hut-SNE (2013, methodology): “We use the condition proposed by [1] to decide whether a cell may be used as a “summary” for all points in that cell.”
The Cosmological simulation code GADGET-2 (2005, methodology): “The hierarchical tree algorithms (Appel, 1985; Barnes & Hut, 1986; Dehnen, 2000) follow a diﬀerent approach, and have no intrinsic resolution limit.”
Fast evaluation of polyharmonic splines in three dimensions (2006, background): “• child either contains pointers to two child panels, child[0] and child[1], or is null if the current panel has no children.”
Discrete-vortex method with novel shedding criterion for unsteady aerofoil flows with intermittent leading-edge vortex shedding (2014, methodology): “Fast summation methods could be used to reduce the computational cost down to O(n log n) (Barnes & Hut 1986) or O(n) (Carrier, Greengard & Rokhlin 1988).”
The many lives of active galactic nuclei: cooling flows, black holes and the luminosities and colour (2005, methodology): “2 This computer is operated by the Computing Centre of the Max Planck Society in Garching, Germany. combining a hierarchical multipole expansion, or ‘tree’ algorithm (Barnes & Hut 1986), and a classical, Fourier transform particle– mesh method (Hockney & Eastwood 1981).”
Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding (2017, methodology): “On the other hand, the repulsive forces Frep,i are approximated at each iteration using the Barnes-Hut Algorithm (Barnes and Hut (1986)), a tree-based algorithm which scales as O(n log n). Despite these accelerations, it can still take many hours to run tSNE on large scRNA-seq datasets. Furthermore,”
Full numerical simulations of catastrophic small body collisions (2008, methodology): “The parallel tree method of Barnes and Hut (1986) is included in the version 8 distribution.”