Quadtrees
The cells of a FlatQuadtree, how deep it splits where the charges crowd, and which cells a Barnes-Hut walk takes as multipoles for one target, drawn with plasma-plots’ plot_quadtree.
Two clusters of charges of both signs on a sparse background. The tree splits every cell holding more than leaf_capacity charges, so it reaches deep inside the clusters and stays shallow around them. plot_quadtree reads the cells straight from the tree: their centres, half widths, depths, children and particle counts.
import numpy as npimport plasma_plotsfrom plasma_plots.trees import barnes_hut_walk, plot_quadtree, quadtree_cells
from tree_d_3d import FlatQuadtree, Quad, direct_field
plasma_plots.set_backend("plotly")plasma_plots.set_math("latex")
rng = np.random.default_rng(4)pos = np.concatenate( [ rng.normal((-0.45, -0.35), 0.1, (900, 2)), rng.normal((0.4, 0.35), 0.18, (900, 2)), rng.uniform(-1.0, 1.0, (300, 2)), ]).T.clip(-0.999, 0.999)charge = rng.choice([-1.0, 1.0], pos.shape[1])tree = FlatQuadtree(pos, charge, Quad(0.0, 0.0, 1.0), leaf_capacity=8)cells = quadtree_cells(tree)print( f"{pos.shape[1]} charges, {int((cells.counts > 0).sum())} cells, depth {cells.depths.max()}")plot_quadtree(tree, points=pos, point_color=charge, title="The tree on 2100 charges")2100 charges, 755 cells, depth 8The leaf capacity sets how far the tree splits. A larger one makes fewer, fuller leaves: a shorter walk with longer direct sums at its end. Coloured by the charges each leaf holds:
with plasma_plots.figure(2, 1, figsize=(6.4, 11.5), gridspec_kw={"hspace": 0.3}) as fig: for ax, capacity in zip(fig, (8, 32)): small = FlatQuadtree(pos, charge, Quad(0.0, 0.0, 1.0), leaf_capacity=capacity) plot_quadtree(small, color="count", ax=ax, title=f"leaf capacity {capacity}")figFor one target the walk starts at the root. A cell of side at distance counts as a single multipole when ; any other cell is opened, down to the leaves, which are summed charge by charge. A small opening angle opens more cells and is more accurate:
target = (0.1, -0.05)with plasma_plots.figure(2, 1, figsize=(6.4, 11.5), gridspec_kw={"hspace": 0.3}) as fig: for ax, theta in zip(fig, (0.3, 0.8)): plot_quadtree(tree, points=pos, target=target, theta=theta, color=None, ax=ax)figThe work of a walk is the multipoles it takes plus the charges in the leaves it sums. Counted with barnes_hut_walk for every charge as a target, against the error of FlatQuadtree.evaluate relative to the direct sum:
exact = direct_field(pos, pos, charge, exclude=np.arange(pos.shape[1]), softening=1e-3)[ 1]thetas = np.array([0.2, 0.3, 0.45, 0.6, 0.8, 1.0])error, work = [], []sample = rng.choice(pos.shape[1], 200, replace=False)for theta in thetas: field = tree.evaluate( pos, exclude=np.arange(pos.shape[1]), theta=theta, softening=1e-3 )[1] error.append(np.abs(field - exact).max() / np.abs(exact).max()) walks = [barnes_hut_walk(cells, pos[:, i], theta) for i in sample] work.append( np.mean([w["accepted"].sum() + cells.counts[w["direct"]].sum() for w in walks]) )with plasma_plots.figure(2, 1, sharex=True, figsize=(6.4, 8.0)) as fig: fig[0].semilogy(thetas, error, "o-") fig[0].set_ylabel("largest field error") fig[1].plot(thetas, work, "o-", color="C1") fig[1].axhline(pos.shape[1], color="gray", linestyle="--", label="direct sum") fig[1].set_ylabel("interactions per target") fig[1].set_xlabel(r"opening angle $\theta$") fig[1].legend()fig