The equations of tree_d_3d.flat_tree , declared on the code that implements them and checked by the tests.
Exact potential (M,) and field (2, M) at targets (2, M), without k_e.
coulomb potential ϕ ( r ) = ∑ j q j ∣ r − r j ∣ 2 + ε 2 \phi(\mathbf r) = \sum_j \frac{q_j}{\sqrt{|\mathbf r - \mathbf r_j|^2 + \varepsilon^2}} ϕ ( r ) = j ∑ ∣ r − r j ∣ 2 + ε 2 q j coulomb field E ( r ) = − ∇ ϕ = ∑ j q j ( r − r j ) ( ∣ r − r j ∣ 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}} E ( r ) = − ∇ ϕ = j ∑ ( ∣ r − r j ∣ 2 + ε 2 ) 3/2 q j ( r − r j ) log potential ϕ ( r ) = − ∑ j q j ln ( ∣ r − r j ∣ 2 + ε 2 ) \phi(\mathbf r) = -\sum_j q_j \ln\left(|\mathbf r - \mathbf r_j|^2 + \varepsilon^2\right) ϕ ( r ) = − j ∑ q j ln ( ∣ r − r j ∣ 2 + ε 2 ) log field E ( r ) = 2 ∑ j q j ( r − r j ) ∣ r − r j ∣ 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} E ( r ) = 2 j ∑ ∣ r − r j ∣ 2 + ε 2 q j ( r − r j ) Assumes raw kernels: the callers multiply by k e = 1 / ( 4 π ε 0 ) k_e = 1/(4\pi\varepsilon_0) k e = 1/ ( 4 π ε 0 ) coulomb: point charges confined to the plane; log: line charges along z z z per unit length, ϕ = − ( λ / 2 π ε 0 ) ln r \phi = -(\lambda/2\pi\varepsilon_0)\ln r ϕ = − ( λ /2 π ε 0 ) ln r Plummer softening ε \varepsilon ε ; the excluded source and zero charges are skipped; a charged pair at r 2 + ε 2 = 0 r^2 + \varepsilon^2 = 0 r 2 + ε 2 = 0 raises Array quadtree for point charges in a plane or for line charges.
split N c e l l > N l e a f , d e p t h < d m a x ⇒ four children of half-width h / 2 , c ± h / 2 N_\mathrm{cell} > N_\mathrm{leaf},\ \ \mathrm{depth} < d_\mathrm{max} \ \Rightarrow\ \text{four children of half-width } h/2,\ \mathbf c \pm h/2 N cell > N leaf , depth < d max ⇒ four children of half-width h /2 , c ± h /2 quadrant k = [ x > x m i d ] + 2 [ y < y m i d ] ( 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}) k = [ x > x mid ] + 2 [ y < y mid ] ( 0 upper left , 1 upper right , 2 lower left , 3 lower right ) coulomb moments Q = ∑ j q j , p = ∑ j q j d j , S = ∑ j q j d j d j T , d j = r j − c Q = \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 Q = j ∑ q j , p = j ∑ q j d j , S = j ∑ q j d j d j T , d j = r j − c log moments a n = ∑ j q j ( z j − c ) n , n = 0 , … , p , z = x + i y a_n = \sum_j q_j (z_j - c)^n, \qquad n = 0, \dots, p, \qquad z = x + iy a n = j ∑ q j ( z j − c ) n , n = 0 , … , p , z = x + i y 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 c , summed directly from each node's particles (no M2M); S \mathsf S S is raw, not traceless cells with ∑ j ∣ q j ∣ = 0 \sum_j |q_j| = 0 ∑ j ∣ q j ∣ = 0 are skipped by the walks; a particle on a dividing line goes left or up Potential (M,) and field (2, M) at targets (2, M), without k_e.
acceptance accept the cell if r ∉ cell and 2 h < θ 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)} accept the cell if r ∈ / cell and 2 h < θ D , D = ∣ r − c ∣ (unsoftened) coulomb multipole ϕ + = Q ρ + p ⋅ R ρ 3 + 1 2 ( 3 R T S R ρ 5 − tr S ρ 3 ) , R = r − c , ρ = D 2 + ε 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} ϕ + = ρ Q + ρ 3 p ⋅ R + 2 1 ( ρ 5 3 R T S R − ρ 3 tr S ) , R = r − c , ρ = D 2 + ε 2 coulomb field E + = Q R ρ 3 + 3 ( p ⋅ R ) R ρ 5 − p ρ 3 + 15 2 ( R T S R ) R ρ 7 − 3 S R ρ 5 − 3 2 tr 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} E + = ρ 3 Q R + ρ 5 3 ( p ⋅ R ) R − ρ 3 p + 2 15 ρ 7 ( R T S R ) R − ρ 5 3 S R − 2 3 ρ 5 tr S R log multipole ϕ + = − a 0 ln ∣ z − c ∣ 2 + 2 ∑ n = 1 p Re ( a n w n ) n , E x − i E y + = 2 ∑ n = 0 p a n w n + 1 , w = 1 z − 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} ϕ + = − a 0 ln ∣ z − c ∣ 2 + 2 n = 1 ∑ p n Re ( a n w n ) , E x − i E y + = 2 n = 0 ∑ p a n w n + 1 , w = z − c 1 leaves leaves: the softened direct sum of direct_field \text{leaves: the softened direct sum of } \texttt{direct\_field} leaves: the softened direct sum of 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 θ = 0 is the exact sum the Coulomb expansion through the quadrupole, from the Taylor series of 1 / ∣ R − d ∣ 1/|\mathbf R - \mathbf d| 1/∣ R − d ∣ with R → ρ R \to \rho R → ρ ; E = − ∇ ϕ \mathbf E = -\nabla\phi E = − ∇ ϕ holds exactly for this softened form accepted log-kernel cells are unsoftened: softening acts on the direct leaf pairs only, an O ( ε 2 / D 2 ) O(\varepsilon^2/D^2) O ( ε 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 + 1 p + 1 p + 1 for the log kernel (3 at the p = 2 p = 2 p = 2 of the test problem) References Built from Potential, shape (n,), and electric field, shape (2, n), at probes (2, n).
coulomb potential ϕ = k e ϕ r a w , E = k e E r a w \phi = k_e\, \phi_\mathrm{raw}, \qquad \mathbf E = k_e\, \mathbf E_\mathrm{raw} ϕ = k e ϕ raw , E = k e E raw log potential ϕ = k e ( ϕ r a w + 2 ln r 0 ∑ j q j ) = − 2 k e ∑ j q j ln r j r 0 \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} ϕ = k e ( ϕ raw + 2 ln r 0 j ∑ q j ) = − 2 k e j ∑ q j ln r 0 r j Assumes the log potential is defined up to a constant: r 0 r_0 r 0 (reference_radius) shifts energies, not forces k e = 1 / ( 4 π ε 0 ) k_e = 1/(4\pi\varepsilon_0) k e = 1/ ( 4 π ε 0 ) by default; SI inputs give SI outputsBuilt from Potential and field at every source, by the FMM.
traversal ( a , b ) → { M2L 2 ( h a + h b ) < θ d a b P2P a = b a leaf, or two leaves split a or b otherwise (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} ( a , b ) → ⎩ ⎨ ⎧ M2L P2P split a or b 2 ( h a + h b ) < θ d ab a = b a leaf, or two leaves otherwise (the larger, not a leaf) m2l b 0 + = a 0 ln t − ∑ k = 1 p a k k t k , b l + = ( − 1 ) l + 1 a 0 l t l − ( − 1 ) l t l ∑ k = 1 k max a k k ( k + l − 1 l ) 1 t k , t = c d s t − c s r c b_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} b 0 + = a 0 ln t − k = 1 ∑ p k t k a k , b l + = l t l ( − 1 ) l + 1 a 0 − t l ( − 1 ) l k = 1 ∑ k m a x k a k ( l k + l − 1 ) t k 1 , t = c dst − c src truncation k max = p (rectangle) , k max = p − l (triangle, symmetric=True ) k_{\max} = p \ \text{(rectangle)}, \qquad k_{\max} = p - l \ \text{(triangle, } \texttt{symmetric=True}\text{)} k m a x = p (rectangle) , k m a x = p − l (triangle, symmetric=True ) l2l b m c h i l d + = ∑ l = m p ( l m ) b l s l − m , s = c c h i l d − c p a r e n t b^\mathrm{child}_m \mathrel{+}= \sum_{l=m}^{p} \binom{l}{m} b_l\, s^{\,l-m}, \qquad s = c_\mathrm{child} - c_\mathrm{parent} b m child + = l = m ∑ p ( m l ) b l s l − m , s = c child − c parent l2p W = ∑ l = 0 p b l u l , ϕ + = − 2 Re W , E x − i E y + = 2 W ′ , u = z i − c l e a f W = \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} W = l = 0 ∑ p b l u l , ϕ + = − 2 Re W , E x − i E y + = 2 W ′ , u = z i − c leaf p2p ϕ i + = − ∑ j q j ln ( r i j 2 + ε 2 ) , E i + = 2 ∑ j q j d i j r i j 2 + ε 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} ϕ i + = − j ∑ q j ln ( r ij 2 + ε 2 ) , E i + = 2 j ∑ r ij 2 + ε 2 q j d ij coulomb moments m α = ∑ j q j ( r j − c ) α , ∣ α ∣ ≤ p (Cartesian, r α = x α x y α 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)} m α = j ∑ q j ( r j − c ) α , ∣ α ∣ ≤ p (Cartesian, r α = x α x y α y ; leaves, then M2M) coulomb taylor n R 2 A γ = − ( 2 n − 1 ) ( t x A γ − e x + t y A γ − e y ) − ( n − 1 ) ( A γ − 2 e x + A γ − 2 e y ) , A 0 = 1 R , R 2 = ∣ 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| n R 2 A γ = − ( 2 n − 1 ) ( t x A γ − e x + t y A γ − e y ) − ( n − 1 ) ( A γ − 2 e x + A γ − 2 e y ) , A 0 = R 1 , R 2 = ∣ t ∣ 2 + ε 2 , n = ∣ γ ∣ 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 T β + = ∣ α ∣ + ∣ β ∣ ≤ p ∑ ( − 1 ) ∣ α ∣ ( α α + β ) m α A α + β ( t ) , ϕ ( c + u ) = β ∑ T β u β , E = − ∇ ϕ Order potential: 3, field: 2 Assumes 0 < θ < 1 0 < \theta < 1 0 < θ < 1 ; every particle is a target; each pair is listed once and used in both directionskernel=\"coulomb\" (CPU only): Cartesian expansions of the softened kernel f = ( ∣ r ∣ 2 + ε 2 ) − 1 / 2 f = (|\mathbf r|^2 + \varepsilon^2)^{-1/2} f = ( ∣ r ∣ 2 + ε 2 ) − 1/2 to total degree p p p (order, default 4), A γ = ∂ γ f / γ ! A_{\boldsymbol\gamma} = \partial^{\boldsymbol\gamma} f / \boldsymbol\gamma! A γ = ∂ γ f / γ ! by the Taylor recurrence; the total-degree truncation makes pair forces exactly antisymmetric; softened throughout, far field includedfmm_at: the same traversal between a tree of the targets and the sources' tree, one way, with exact sums between their leavesthe local expansion Φ L ( z ) = ∑ l b l ( z − c ) l \Phi_L(z) = \sum_l b_l (z - c)^l Φ L ( z ) = ∑ l b l ( z − c ) l of degree p p p about each cell centre; ln t \ln t ln t on the principal branch, which shifts b 0 b_0 b 0 by 2 π i a 0 2\pi i a_0 2 π i a 0 and drops out of Re \operatorname{Re} 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 p p p set the accuracy the error of an M2L is O ( ( r / d ) p + 1 ) O((r/d)^{p+1}) O (( r / d ) p + 1 ) in the potential and O ( ( r / d ) p ) O((r/d)^{p}) O (( r / d ) p ) in the field, r / d r/d r / d the cluster size over the cell distance; the declared orders are those at the p = 2 p = 2 p = 2 of the test problem References Built from