Skip to content
Projects

Kernels

Download notebookView on GitHubRun when the site was built.

The two interaction kernels, point charges and line charges, and the compiled compute kernels behind every tree walk, FMM and direct sum: Pyccel on the CPU, CUDA through CuPy, Metal through MLX.

kernel="coulomb" treats every particle as a point charge in the plane, with potential q/rq/r and field q d/r3q\,\mathbf d/r^3. kernel="log" makes it an infinite line charge along zz, with potential −2qln⁡r-2q\ln r and field 2q d/r22q\,\mathbf d/r^2: the 2D Poisson kernel of planar PIC codes. All sums return the raw values, without kek_e.

import time
import cunumpy as xp
import numpy as np
import plasma_plots
from tree_d_3d import FlatQuadtree, Quad, direct_field, kernels_compiled
from tree_d_3d.kernels import KERNEL_NAMES
plasma_plots.set_backend("plotly")
r = np.logspace(-2, 1, 50)
targets = np.stack((r, np.zeros_like(r)))
charge = (np.zeros((2, 1)), np.ones(1))
with plasma_plots.figure(1, 1) as fig:
for kernel in ("coulomb", "log"):
_, field = direct_field(targets, *charge, kernel=kernel)
fig[0].loglog(r, np.asarray(field)[0], label=kernel)
fig[0].set_xlabel("distance r")
fig[0].set_ylabel("field of a unit charge")
fig[0].legend()
fig
Loading figure…

Both kernels run through the same three methods. direct_field sums exactly, in O(NM)O(NM). FlatQuadtree.evaluate walks the Barnes-Hut tree at opening angle theta, in O(Mlog⁡N)O(M \log N). For line charges, FlatQuadtree.fmm is the fast multipole method, O(N)O(N) for the fields at all sources.

rng = np.random.default_rng(0)
print(f"{'N':>7s} {'direct':>8s} {'tree':>8s} {'FMM':>8s} FMM error")
for n in (2_000, 8_000, 32_000):
pos = rng.uniform(-1.0, 1.0, (2, n))
q = rng.choice([-1.0, 1.0], n)
own = np.arange(n)
start = time.perf_counter()
_, exact = direct_field(pos, pos, q, kernel="log", exclude=own)
t_direct = time.perf_counter() - start
start = time.perf_counter()
tree = FlatQuadtree(pos, q, Quad(0.0, 0.0, 1.0), kernel="log", order=16)
tree.evaluate(pos, exclude=own, theta=0.5)
t_tree = time.perf_counter() - start
start = time.perf_counter()
tree = FlatQuadtree(
pos, q, Quad(0.0, 0.0, 1.0), kernel="log", order=16, leaf_capacity=32
)
_, field = tree.fmm(theta=0.5)
t_fmm = time.perf_counter() - start
error = np.abs(np.asarray(field) - np.asarray(exact)).max() / np.abs(exact).max()
print(f"{n:7d} {t_direct:7.3f}s {t_tree:7.3f}s {t_fmm:7.3f}s {error:.1e}")
N direct tree FMM FMM error
2000 0.015s 4.326s 6.715s 1.1e-09
8000 0.224s 0.021s 0.020s 1.4e-10
32000 3.576s 0.107s 0.070s 2.7e-10

The compute kernels live in tree_d_3d.kernels, one folder per kernel. Each folder has the same routine in up to four versions:

  • <name>_pyccel.py, compiled to C/Fortran by Pyccel on first use and cached (TREE_D_3D_KERNEL_CACHE; TREE_D_3D_OPENMP sets the threads);
  • <name>_numpy.py, used if Pyccel is not available;
  • <name>_cuda.cu, compiled by NVRTC when the arrays are CuPy arrays;
  • <name>_metal.py, run through MLX on Apple GPUs (float32).

The backend follows cunumpy: cunumpy.set_backend("cupy") puts the trees on the GPU with no other change. kernels_compiled() tells whether the CPU versions compiled.

print(f"backend: {xp.get_backend()}, kernels compiled: {kernels_compiled()}")
print(f"{len(KERNEL_NAMES)} kernels:", ", ".join(KERNEL_NAMES))
backend: numpy, kernels compiled: True
14 kernels: quadtree_quadrants, quadtree_scatter, quadtree_moments, evaluate_quadtree, direct_sum, pair_energy, log_quadtree_moments, evaluate_log_quadtree, direct_log_sum, fmm_traverse, fmm_m2l, fmm_downward, fmm_evaluate, soften_pairs

compiled=False runs a kernel’s plain-Python version instead. It is the readable reference the compiled versions are tested against, and far slower: use it to check results, not to compute them.

pos = rng.uniform(-1.0, 1.0, (2, 300))
q = rng.choice([-1.0, 1.0], 300)
for compiled in (True, False):
start = time.perf_counter()
tree = FlatQuadtree(pos, q, Quad(0.0, 0.0, 1.0), compiled=compiled)
phi, field = tree.evaluate(pos, exclude=np.arange(300), theta=0.5)
print(
f"compiled={compiled!s:5s}: {time.perf_counter() - start:.4f} s, field[0, 0] = {float(field[0, 0]):.12f}"
)
compiled=True : 0.0007 s, field[0, 0] = -111.991570852135
compiled=False: 0.0691 s, field[0, 0] = -111.991570852135