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)$.

- (5 pts) Name algorithms that break $\mathcal{O}(N^2)$ for $N$-body problem. Specify their complexities. Estimate how much memory and what time requires to estimate all $N$ potentials $V({\bf y}_j)$ for $N=300$ billion particles with naive $\mathcal{O}(N^2)$ summation and $\mathcal{O}(N\log N)$, $\mathcal{O}(N)$ algorithms on a supercomputer (constants hidden in $\mathcal{O}$ can be found in lectures).

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.

- (10 pts) Propose an algorithm for the quadtree construction. Can you reach $\mathcal{O}(N)$ memory for the storage? Propose a way to store the tree and write the program that computes the tree, given the location of the particles. What do you need to store in each node of the tree?

- (20 pts) Implement Barnes-Hut algorithm. The program should consist of three parts:
- Tree construction given the location of the particles and geometric constant $\theta$
- Filling the information in the tree (computing the charges and geometric centers)
- Computing the product

- (5 pts) Compare the results computed by direct evaluation and Barnes-Hut algorithm. Make sure that you got linear complexity. Study the dependance of accuracy and computational cost on the geometric parameter $\theta$

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.

- (20 pts) Now that you are a given a tree from the previous task, code the Barnes-Hut with two trees. The key differences are:
- You need to create the interaction list
- You also need to build M2L and L2L operators (in standard BH only M2M operator is used)

- (5 pts) Compare performance and accuracy of the standard and 2-tree BH. Which one is faster?

```
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 [ ]:
```