Skip to content
Projects

Barnes-Hut tree

The Barnes-Hut tree, and how a quadtree approximates distant charges.

Runs the experiments behind FlatQuadtree.evaluate, the library’s Barnes-Hut tree walk for point and line charges, and saves one figure per claim:

Source: examples/barnes_hut_tree.py. Run it yourself with python examples/barnes_hut_tree.py [--output examples/output] [--quick] (needs pip install "tree-d-3d[examples]").

two colliding star clusters evolved with the pure-Python Barnes-Hut gravity solver, animated, with the quadtree redrawn every frame.two colliding star clusters evolved with the pure-Python Barnes-Hut gravity solver, animated, with the quadtree redrawn every frame.Loading figure…

two colliding star clusters evolved with the pure-Python Barnes-Hut gravity solver, animated, with the quadtree redrawn every frame.

a cloud of random charges of both signs and the cells of the quadtree built on them, colored by depth (`plasma_plots.plot_quadtree`): cells shrink where particles are dense and stay large where they are sparse.a cloud of random charges of both signs and the cells of the quadtree built on them, colored by depth (`plasma_plots.plot_quadtree`): cells shrink where particles are dense and stay large where they are sparse.Loading figure…

a cloud of random charges of both signs and the cells of the quadtree built on them, colored by depth (plasma_plots.plot_quadtree): cells shrink where particles are dense and stay large where they are sparse.

for one target particle (the star), the cells the walk accepts as single multipoles (far enough, orange) and the leaves it sums particle by particle (too close, red); the other cells are opened on the way down.for one target particle (the star), the cells the walk accepts as single multipoles (far enough, orange) and the leaves it sums particle by particle (too close, red); the other cells are opened on the way down.Loading figure…

for one target particle (the star), the cells the walk accepts as single multipoles (far enough, orange) and the leaves it sums particle by particle (too close, red); the other cells are opened on the way down.

field error against the direct sum, and wall-clock time, both against the opening angle theta: smaller theta is more accurate and slower.field error against the direct sum, and wall-clock time, both against the opening angle theta: smaller theta is more accurate and slower.Loading figure…

field error against the direct sum, and wall-clock time, both against the opening angle theta: smaller theta is more accurate and slower.

wall-clock time against N for the direct sum and the tree walk, on a log-log plot, next to reference slopes for their N^2 and N log N complexities.wall-clock time against N for the direct sum and the tree walk, on a log-log plot, next to reference slopes for their N^2 and N log N complexities.Loading figure…

wall-clock time against N for the direct sum and the tree walk, on a log-log plot, next to reference slopes for their N^2 and N log N complexities.

--quick uses fewer particles and a narrower N range (well under a minute instead of a few minutes). Needs Plotly (pip install 'tree-d-3d[examples]').