Consider the $N$-body problem $$ V({\bf y}_j) = \sum_{i=1}^N G({\bf x}_i, {\bf y}_j) q_i, \quad j=1,\dots,N, $$ where ${\bf x}_i$ is the location of source charges and ${\bf y}_j$ is the location of receivers where the potential $V$ is measured. For simplicity in this pset sources and receivers are the same points: ${\bf x}_i = {\bf y}_i$, $i=1,\dots,N$. The naive summation yields $\mathcal{O}(N^2)$ complexity, which is prohibitive if $N$ is large. This problem set is devoted to algorithms that break the $\mathcal{O}(N^2)$.
The Barnes-Hut (BH) idea is quite simple. First, we separate our particles in a quad-tree structure of particle groups. If the group on some tree level is sufficiently far away from a certain particle, we can approximate its potential by using its center of mass. If it is not, we compute its influence recursively by using lower tree levels. The accuracy of the Barnes-Hut algorithm depends on the choise of parameter $\theta = s / d$, where $s$ is the width of the region represented by the internal node, and $d$ is the distance between the body and the node's center-of-mass.
In order to break $\log$ term in $\mathcal{O}(N \log N)$ for the Barnes-Hut algorithm a second tree can be used. This almost leads us to the FMM algorithm with only one exception: only one term in the multipole expansion is used.
In [ ]:
Consider an ideally conducting sphere $\Omega\subset\mathbb{R}^3$, which is attached to a $1$ V battery.
(5 pts) Write first kind Fredholm integral equation on $\partial \Omega$
(20 pts) Using BEM++ write a Python program solves this integral equation
(10 pts) Write a function that evaluates potenital from the obtained solution at the given point of $\mathbb{R}^3$
(5 pts) Plot the depenedce of the potential on a half-line from the center of the sphere. Compare it with the analytical solution by plotting obtained solution for different number of grid points and the analytic solution on one plot
In [ ]: