Fixed-order planar Laplace fast multipole procedure

Use the data, quadtree and interaction decomposition of Finite planar quadtree and separated interaction lists. Fix an expansion order $p\ge 1$. If two different labels have the same position, return status collision before evaluating any singular interaction: the requested potential is undefined. Otherwise take as input a finite quadtree from the definition, together with its point-to-cell membership arrays and leaf threshold $s$. For $N=0$ return empty outputs. For $N\ge 1$, construct $\mathcal{F}$ and $\mathcal{N}$ by the recursive decomposition in the definition. The tree and point-to-cell membership are preprocessing inputs; their construction is not part of the arithmetic passes below.

Using the supplied membership data, make a root-first list of nonempty cells: at each nonempty internal cell inspect its four children and recurse only into children $E$ with $I_E\mathrm{\ne }\mathrm{\varnothing }$; never descend into an empty subtree. Use the reverse list order for the bottom-up pass and the root-first order for the top-down pass. Use exact complex arithmetic throughout. For each nonempty leaf $C$ form the particle-to-multipole (P2M) moments $M_n(C)={\sum }_{j\in I_C}{q}_j(z_j-c_C{)}^n,0\le n\le p\mathrm{.}$ For the upward multipole-to-multipole (M2M) pass, process nonempty internal cells bottom-up. For each such parent $C$ and each $0\le n\le p$, form its moments from its nonempty children by $M_n(C)={\sum }_{\begin{array}{c}E\text{ child of }C\\ I_E\mathrm{\ne }\mathrm{\varnothing }\end{array}}{\sum }_{r=0}^n\left(\genfrac{}{}{0px}{}{n}{r}\right)(c_E-c_C{)}^{n-r}{M}_r(E)\mathrm{.}$ An empty child has zero moments and is skipped. Thus the upward pass visits only parent-child edges whose two cells are nonempty.

Initialize the local coefficient vector of every nonempty cell to zero before processing any far pair. For each far pair $(C,D)$ set $\delta =c_D-c_C$, $R=\mathrm{\mid }\delta \mathrm{\mid }$, choose the fixed logarithm $L_{CD}$, and add to the target cell $D$'s local coefficients the multipole-to-local (M2L) coefficients $L_0(D)+=M_0(C)L_{CD}(\delta )-{\sum }_{n=1}^p\frac{M_n(C)}{n{\delta }^n},$ $L_k(D)+=(-1{)}^{k+1}(\frac{M_0(C)}{k{\delta }^k}+{\sum }_{n=1}^p\left(\genfrac{}{}{0px}{}{n+k-1}{k}\right)\frac{M_n(C)}{n{\delta }^{n+k}}),1\le k\le p\mathrm{.}$ After all M2L additions, perform a top-down downward local-to-local (L2L) pass over parent-child edges whose two cells are nonempty. For each parent $D$ and each nonempty child $E$, add $L_j(E)+={\sum }_{k=j}^p\left(\genfrac{}{}{0px}{}{k}{j}\right)L_k(D)(c_E-c_D{)}^{k-j},0\le j\le p\mathrm{.}$ For a target $i$ in leaf $D$, return the far potential ${\sum }_{k=0}^p{L}_k(D)(z_i-c_D{)}^k$ and far derivative ${\sum }_{k=1}^{p}k{L}_k(D)(z_i-c_D{)}^{k-1}$. Add the exact direct near contributions $q_j{L}_{ji}$ and $q_j\mathrm{/}(z_i-z_j)$, respectively, for $(j,i)\in \mathcal{N}$. Denote the resulting potential and derivative approximations by ${\tilde{u}}_i$ and ${\tilde{g}}_i$, respectively. The derivative output differentiates the truncated local polynomial and adds the exact near derivatives; its value is independent of logarithm branches.