Skip to content
Projects

Trees and FMM

The equations of tree_d_3d.flat_tree, declared on the code that implements them and checked by the tests.

direct_field

functionsource

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

coulomb potential
ϕ(r)=∑jqj∣r−rj∣2+ε2\phi(\mathbf r) = \sum_j \frac{q_j}{\sqrt{|\mathbf r - \mathbf r_j|^2 + \varepsilon^2}}
coulomb field
E(r)=−∇ϕ=∑jqj (r−rj)(∣r−rj∣2+ε2)3/2\mathbf E(\mathbf r) = -\nabla\phi = \sum_j \frac{q_j\,(\mathbf r - \mathbf r_j)}{\left(|\mathbf r - \mathbf r_j|^2 + \varepsilon^2\right)^{3/2}}
log potential
ϕ(r)=−∑jqjln⁡(∣r−rj∣2+ε2)\phi(\mathbf r) = -\sum_j q_j \ln\left(|\mathbf r - \mathbf r_j|^2 + \varepsilon^2\right)
log field
E(r)=2∑jqj (r−rj)∣r−rj∣2+ε2\mathbf E(\mathbf r) = 2\sum_j \frac{q_j\,(\mathbf r - \mathbf r_j)}{|\mathbf r - \mathbf r_j|^2 + \varepsilon^2}
Assumes
  • raw kernels: the callers multiply by ke=1/(4πε0)k_e = 1/(4\pi\varepsilon_0)
  • coulomb: point charges confined to the plane; log: line charges along zz per unit length, ϕ=−(λ/2πε0)ln⁡r\phi = -(\lambda/2\pi\varepsilon_0)\ln r
  • Plummer softening ε\varepsilon; the excluded source and zero charges are skipped; a charged pair at r2+ε2=0r^2 + \varepsilon^2 = 0 raises

FlatQuadtree

classsource

Array quadtree for point charges in a plane or for line charges.

split
Ncell>Nleaf,  depth<dmax ⇒ four children of half-width h/2, c±h/2N_\mathrm{cell} > N_\mathrm{leaf},\ \ \mathrm{depth} < d_\mathrm{max} \ \Rightarrow\ \text{four children of half-width } h/2,\ \mathbf c \pm h/2
quadrant
k=[x>xmid]+2 [y<ymid](0 upper left, 1 upper right, 2 lower left, 3 lower right)k = [x > x_\mathrm{mid}] + 2\,[y < y_\mathrm{mid}] \qquad (0\text{ upper left},\ 1\text{ upper right},\ 2\text{ lower left},\ 3\text{ lower right})
coulomb moments
Q=∑jqj,p=∑jqjdj,S=∑jqj djdjT,dj=rj−cQ = \sum_j q_j, \qquad \mathbf p = \sum_j q_j \mathbf d_j, \qquad \mathsf S = \sum_j q_j\, \mathbf d_j \mathbf d_j^{\mathsf T}, \qquad \mathbf d_j = \mathbf r_j - \mathbf c
log moments
an=∑jqj(zj−c)n,n=0,…,p,z=x+iya_n = \sum_j q_j (z_j - c)^n, \qquad n = 0, \dots, p, \qquad z = x + iy
Assumes
  • a square root cell; built level by level, breadth first, with a stable partition: the order inside a cell is the input order
  • moments about the geometric cell centre c\mathbf c, summed directly from each node's particles (no M2M); S\mathsf S is raw, not traceless
  • cells with ∑j∣qj∣=0\sum_j |q_j| = 0 are skipped by the walks; a particle on a dividing line goes left or up

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

field_at

functionsource

Potential, shape (n,), and electric field, shape (2, n), at probes (2, n).

coulomb potential
ϕ=ke ϕraw,E=ke Eraw\phi = k_e\, \phi_\mathrm{raw}, \qquad \mathbf E = k_e\, \mathbf E_\mathrm{raw}
log potential
ϕ=ke(ϕraw+2ln⁡r0∑jqj)=−2ke∑jqjln⁡rjr0\phi = k_e\left(\phi_\mathrm{raw} + 2\ln r_0 \sum_j q_j\right) = -2k_e \sum_j q_j \ln\frac{r_j}{r_0}
Assumes
  • the log potential is defined up to a constant: r0r_0 (reference_radius) shifts energies, not forces
  • ke=1/(4πε0)k_e = 1/(4\pi\varepsilon_0) by default; SI inputs give SI outputs
Built from

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