Skip to content
Projects

Overview

tree-d-3d computes the electrostatic field of N charges in a plane, in free space, and moves the charges in it, with an optional uniform magnetic field BzB_z. Nothing is put on a mesh: the field is a sum over the charges, made fast by a Barnes-Hut tree walk or, for line charges, a fast multipole method, and conductors enter as charged panels on their surfaces. Two interaction kernels, chosen per tree with kernel=:

  • "coulomb": point charges with the 3D Coulomb interaction, confined to the plane;
  • "log": infinite line charges along zz, the Green’s function of 2D Poisson (2D Cartesian PIC).

Each equation on these pages is declared on the code that implements it, as a method card, and checked by the tests: eighteen closed forms against SymPy rules, five discretisations against their order of convergence. The pages of the section list the cards module by module; this one shows how they fit together.

  1. Kernels. The exact softened sums of both kernels, ϕ=∑jqj/r2+ε2\phi = \sum_j q_j/\sqrt{r^2 + \varepsilon^2} and ϕ=−∑jqjln⁡(r2+ε2)\phi = -\sum_j q_j \ln(r^2 + \varepsilon^2), define the model; direct_field evaluates them in O(NM)O(NM).
  2. Tree walk. A quadtree, built level by level, carries the moments of every cell about its centre. The walk replaces a cell that looks small enough from the target by its expansion, through the quadrupole for point charges and to order pp in complex form for line charges, in O(log⁡N)O(\log N) per target:

evaluate

functionsource

Potential (M,) and field (2, M) at targets (2, M), without k_e.

acceptance
accept the cell if r∉cell  and  2h<θD,D=∣r−c∣ (unsoftened)\text{accept the cell if } \mathbf r \notin \text{cell} \ \text{ and }\ 2h < \theta D, \qquad D = |\mathbf r - \mathbf c|\ \text{(unsoftened)}
coulomb multipole
ϕ+=Qρ+p⋅Rρ3+12(3 RTSRρ5−tr⁡Sρ3),R=r−c,ρ=D2+ε2\phi \mathrel{+}= \frac{Q}{\rho} + \frac{\mathbf p\cdot\mathbf R}{\rho^3} + \frac12\left(\frac{3\,\mathbf R^{\mathsf T}\mathsf S\mathbf R}{\rho^5} - \frac{\operatorname{tr}\mathsf S}{\rho^3}\right), \qquad \mathbf R = \mathbf r - \mathbf c, \quad \rho = \sqrt{D^2 + \varepsilon^2}
coulomb field
E+=QRρ3+3(p⋅R)Rρ5−pρ3+152(RTSR)Rρ7−3 SRρ5−32tr⁡S Rρ5\mathbf E \mathrel{+}= \frac{Q\mathbf R}{\rho^3} + \frac{3(\mathbf p\cdot\mathbf R)\mathbf R}{\rho^5} - \frac{\mathbf p}{\rho^3} + \frac{15}{2}\frac{(\mathbf R^{\mathsf T}\mathsf S\mathbf R)\mathbf R}{\rho^7} - \frac{3\,\mathsf S\mathbf R}{\rho^5} - \frac32\frac{\operatorname{tr}\mathsf S\,\mathbf R}{\rho^5}
log multipole
ϕ+=−a0ln⁡∣z−c∣2+2∑n=1pRe⁡(anwn)n,Ex−iEy+=2∑n=0panwn+1,w=1z−c\phi \mathrel{+}= -a_0 \ln|z - c|^2 + 2\sum_{n=1}^{p} \frac{\operatorname{Re}(a_n w^n)}{n}, \qquad E_x - iE_y \mathrel{+}= 2\sum_{n=0}^{p} a_n w^{n+1}, \qquad w = \frac{1}{z - c}
leaves
leaves: the softened direct sum of direct_field\text{leaves: the softened direct sum of } \texttt{direct\_field}
Order
coulomb: 3, log: 3
Assumes
  • one target at a time, an explicit stack; the cell holding the target is always opened, whatever θ\theta and ε\varepsilon; θ=0\theta = 0 is the exact sum
  • the Coulomb expansion through the quadrupole, from the Taylor series of 1/∣R−d∣1/|\mathbf R - \mathbf d| with R→ρR \to \rho; E=−∇ϕ\mathbf E = -\nabla\phi holds exactly for this softened form
  • accepted log-kernel cells are unsoftened: softening acts on the direct leaf pairs only, an O(ε2/D2)O(\varepsilon^2/D^2) difference in the far field
  • the order is in the size of an accepted cell's charges over its distance, so in θ\theta: 3 through the quadrupole, p+1p + 1 for the log kernel (3 at the p=2p = 2 of the test problem)
References
Built from
  1. Fast multipole method: a dual-tree traversal pairs well-separated cells, whose multipoles become local expansions (M2L), shifted down the tree (L2L) and evaluated at the particles (L2P), in O(N)O(N); complex expansions for line charges, Cartesian ones of the softened kernel for point charges (on the CPU). fmm_at runs it at other points, with a tree of its own over them:

fmm

functionsource

Potential and field at every source, by the FMM.

traversal
(a,b)→{M2L2 (ha+hb)<θ dabP2Pa=b a leaf, or two leavessplit a or botherwise (the larger, not a leaf)(a, b) \to \begin{cases} \text{M2L} & \sqrt2\,(h_a + h_b) < \theta\, d_{ab} \\ \text{P2P} & a = b \text{ a leaf, or two leaves} \\ \text{split } a \text{ or } b & \text{otherwise (the larger, not a leaf)} \end{cases}
m2l
b0+=a0ln⁡t−∑k=1pakk tk,bl+=(−1)l+1a0l tl−(−1)ltl∑k=1kmax⁡akk(k+l−1l)1tk,t=cdst−csrcb_0 \mathrel{+}= a_0\ln t - \sum_{k=1}^{p}\frac{a_k}{k\,t^k}, \qquad b_l \mathrel{+}= \frac{(-1)^{l+1}a_0}{l\,t^l} - \frac{(-1)^l}{t^l}\sum_{k=1}^{k_{\max}}\frac{a_k}{k}\binom{k+l-1}{l}\frac{1}{t^k}, \qquad t = c_\mathrm{dst} - c_\mathrm{src}
truncation
kmax⁡=p (rectangle),kmax⁡=p−l (triangle, symmetric=True)k_{\max} = p \ \text{(rectangle)}, \qquad k_{\max} = p - l \ \text{(triangle, } \texttt{symmetric=True}\text{)}
l2l
bmchild+=∑l=mp(lm)bl s l−m,s=cchild−cparentb^\mathrm{child}_m \mathrel{+}= \sum_{l=m}^{p} \binom{l}{m} b_l\, s^{\,l-m}, \qquad s = c_\mathrm{child} - c_\mathrm{parent}
l2p
W=∑l=0pblul,ϕ+=−2Re⁡W,Ex−iEy+=2W′,u=zi−cleafW = \sum_{l=0}^{p} b_l u^l, \qquad \phi \mathrel{+}= -2\operatorname{Re} W, \qquad E_x - iE_y \mathrel{+}= 2W', \qquad u = z_i - c_\mathrm{leaf}
p2p
ϕi+=−∑jqjln⁡(rij2+ε2),Ei+=2∑jqj dijrij2+ε2\phi_i \mathrel{+}= -\sum_j q_j \ln\left(r_{ij}^2 + \varepsilon^2\right), \qquad \mathbf E_i \mathrel{+}= 2\sum_j \frac{q_j\, \mathbf d_{ij}}{r_{ij}^2 + \varepsilon^2}
coulomb moments
mα=∑jqj(rj−c)α,∣α∣≤p(Cartesian, rα=xαxyαy; leaves, then M2M)m_{\boldsymbol\alpha} = \sum_j q_j (\mathbf r_j - \mathbf c)^{\boldsymbol\alpha}, \quad |\boldsymbol\alpha| \le p \qquad \text{(Cartesian, } \mathbf r^{\boldsymbol\alpha} = x^{\alpha_x} y^{\alpha_y}\text{; leaves, then M2M)}
coulomb taylor
nR2Aγ=−(2n−1)(txAγ−ex+tyAγ−ey)−(n−1)(Aγ−2ex+Aγ−2ey),A0=1R,R2=∣t∣2+ε2,n=∣γ∣n R^2 A_{\boldsymbol\gamma} = -(2n - 1)\left(t_x A_{\boldsymbol\gamma - \mathbf e_x} + t_y A_{\boldsymbol\gamma - \mathbf e_y}\right) - (n - 1)\left(A_{\boldsymbol\gamma - 2\mathbf e_x} + A_{\boldsymbol\gamma - 2\mathbf e_y}\right), \quad A_{\mathbf 0} = \frac1R, \quad R^2 = |\mathbf t|^2 + \varepsilon^2, \quad n = |\boldsymbol\gamma|
coulomb m2l
Tβ+=∑∣α∣+∣β∣≤p(−1)∣α∣(α+βα)mα Aα+β(t),ϕ(c+u)=∑βTβ uβ,E=−∇ϕT_{\boldsymbol\beta} \mathrel{+}= \sum_{|\boldsymbol\alpha| + |\boldsymbol\beta| \le p} (-1)^{|\boldsymbol\alpha|} \binom{\boldsymbol\alpha + \boldsymbol\beta}{\boldsymbol\alpha} m_{\boldsymbol\alpha}\, A_{\boldsymbol\alpha + \boldsymbol\beta}(\mathbf t), \qquad \phi(\mathbf c + \mathbf u) = \sum_{\boldsymbol\beta} T_{\boldsymbol\beta}\, \mathbf u^{\boldsymbol\beta}, \quad \mathbf E = -\nabla\phi
Order
potential: 3, field: 2
Assumes
  • 0<θ<10 < \theta < 1; every particle is a target; each pair is listed once and used in both directions
  • kernel=\"coulomb\" (CPU only): Cartesian expansions of the softened kernel f=(∣r∣2+ε2)−1/2f = (|\mathbf r|^2 + \varepsilon^2)^{-1/2} to total degree pp (order, default 4), Aγ=∂γf/γ!A_{\boldsymbol\gamma} = \partial^{\boldsymbol\gamma} f / \boldsymbol\gamma! by the Taylor recurrence; the total-degree truncation makes pair forces exactly antisymmetric; softened throughout, far field included
  • fmm_at: the same traversal between a tree of the targets and the sources' tree, one way, with exact sums between their leaves
  • the local expansion ΦL(z)=∑lbl(z−c)l\Phi_L(z) = \sum_l b_l (z - c)^l of degree pp about each cell centre; ln⁡t\ln t on the principal branch, which shifts b0b_0 by 2πia02\pi i a_0 and drops out of Re⁡\operatorname{Re}
  • the triangle truncation makes the mutual pair forces exactly antisymmetric (same error order, larger constant)
  • log kernel: softening acts on the P2P pairs only; no automatic error control: θ\theta and pp set the accuracy
  • the error of an M2L is O((r/d)p+1)O((r/d)^{p+1}) in the potential and O((r/d)p)O((r/d)^{p}) in the field, r/dr/d the cluster size over the cell distance; the declared orders are those at the p=2p = 2 of the test problem
References
Built from
  1. Macroparticles carry a weight on mass and charge, so q/mq/m is kept.
  2. Particle pusher: an electric half-kick, the exact gyration in BzB_z over the step, another half-kick; second order, velocity Verlet at Bz=0B_z = 0. Absorbing walls and simgeometry objects remove the particles that cross them.
  3. Boundaries. Two grounded plates by a conformal map of the strip onto the half-plane, where one image per charge makes the plates equipotentials, and conductors at prescribed potentials by the boundary-integral (panel) method: an induced line-charge density on each surface, piecewise constant on straight panels, collocated at their midpoints. The free charges of a meshless space-charge model (a gun, a beam) enter both as sources.

The reference tree is the walk of step 2 as a readable object tree. Two codes stand beside the pipeline: the smooth-membership FMM, a NumPy prototype whose forces are the exact gradient of a smooth energy, and the classic gravitational Barnes-Hut code.

The kernels return raw potentials and fields; the callers multiply by ke=1/(4πε0)k_e = 1/(4\pi\varepsilon_0) (K_E) or by the k_e they are given, so SI inputs give SI outputs. Line charges are per unit length (C/m), and their potential is defined up to a constant: reference_radius r0r_0 makes it −2keqln⁡(r/r0)-2k_e q \ln(r/r_0). Complex notation z=x+iyz = x + iy, with Ex−iEyE_x - iE_y the conjugate field. Per-particle arrays with a component axis are component-major, (2,N)(2, N).

  • No 3D geometry or octree yet: positions, fields and trees are planar.
  • No GPU version of the Coulomb FMM or of fmm_at; the walk keeps the Coulomb quadrupole; no error estimate or automatic choice of θ\theta and pp.
  • For line charges, softening only in the direct pairs: the far cells of the log tree and the FMM are unsoftened (the smooth-membership FMM has a compact softening with an exact far field).
  • No periodic boundaries, dielectrics or Neumann conditions; no conductor at infinity; the electrode system is solved directly (no FMM-accelerated GMRES); no electrodes inside ElectrostaticSimulation (pair it with BoundaryIntegralElectrodes by hand).
  • No magnetic self-fields, induction, time-dependent or non-uniform BB; no relativity, radiation, collisions or emission in the library (the examples add some of them).

Besides the checks of the cards, the tests compare the flat tree with the reference tree node for node, every compiled kernel with its Python source and its NumPy, CUDA (emulated) and Metal versions, the walk and the FMM with the direct sum against θ\theta and pp, the exact cyclotron orbit, energy and momentum over many steps, a self-similarly expanding disk of line charges, the grounded circle, the cylindrical capacitor and an L-shaped conductor against their closed forms, and the strip against charged sheets.