Fast Multipole Method in 3D

Question

I am writing a FMM (Fast Multipole Method) algorithm in 3D. I generated the mesh and, currently, I am developing the expansion and the three (M2M, M2L, L2L) translation operators using spherical harmonics. See reference [1], more specifically, these equations are taken from equation numbers 3.36, 3.37, 3.55, 3.56, 3.57.

I am confused about how to apply the operators and I can't seem to grasp how to apply these effectively. So far my aim is to (after the mesh generation of course):

1 - Perform multipole expansions at the finest level

This as I understand is conducted using these equations

$$\phi(P) = \sum_{n=0}^\infty \sum_{m=-n}^n \frac{M_n^m}{r^{n+1}} Y_n^m(\theta,\phi) \enspace ,$$

where,

$$M_n^m=\sum_i q_i \rho_i^n Y_n^{-m}(\alpha_i,\beta_i) \enspace .$$

In the above equations $P(r,\theta,\phi)$ are the coordinates of the center of the cube and $Q_i(\rho_i,\alpha_i,\beta_i)$ are the source points present in each cube being evaluated with $q_i$ as their corresponding weight for each source point.

2 - Perform the upward pass (M2M)

The translator operators for instance the M2M (i.e. multipole-to-multipole) in the upward pass have the following equations:

$$\phi(G) = \sum_{j=0}^\infty \sum_{k=-j}^j \frac{M_j^k}{r^{j+1}} Y_j^k(\theta,\phi)$$

where, $$M_j^k=\sum_{n=0}^j \sum_{m=-n}^n \frac{O_{j-n}^{k-m} i^{|k|-|m|-|k-m|} A_n^m A_{j-n}^{k-m} \rho^n Y_n^{-m}(\alpha,\beta) }{A_j^k}$$

with

$$A_n^m=\frac{(-1)^n}{\sqrt{(n-m)!(n+m)!}}$$

In the above equations, $G(r,\theta,\phi)$ is the center of the parent cube and $P(\rho,\alpha,\beta)$ is the coordinates of the child cube's center.

Here's where I am basically stuck at:

What is $O_{j-n}^{k-m}$?

Is it the multipole expansions I performed before initiating the M2M translations ?

is it the mulipole moment that was used to compute the multipole expansion before starting the M2M (i.e. $M_n^m$)? if so, then each parent will have 8 children in the level directly above it, hence there exists multiple $M_n^m$, how then should I choose which one to implement in the translation M2M operation in place of the $O_{j-n}^{k-m}$?

P.S.: as you might have noticed already, this is the first time I am implementing the FMM and specifically in 3D. I have to accomplish this as it is a minor step in a larger project with an approaching deadline, hence I appreciate all help anyone can provide.

Reference

[1] Greengard, Leslie. "The rapid evaluation of potential fields in particle systems. ACM Distinguished Dissertations." (1988).

Answer 1

So this answer is supposed to help others trying to implement the shift operators themselves while experiencing delimited knowledge about the method.

The fast multipole method's algorithm is dependent upon the following steps:

1- At the finest level, start calculating multipole expansions in each and every partition. Usually you take the expansion at the center of that partition - but maybe for certain applications one might venture and try different locations?

2- Start the upward pass. This is just the aggregation of the previously calculated expansions and translating them up the tree until the coarsest level is reached. The aggregation is just the multipole-to-multipole shift from a current expansion situated at this level to it's parent. Usually if the partitioning is based on an octree then each 8 children are summed after translation to their corresponding parent. And this goes on all the way reaching level 0.

3- Start the downward pass. In this pass there are two shift operations involved: multipole-to-local and local-to-local. The multipole-to-local shift starts from level 2 and goes all the way down to the finest level. In this translation, which by the way is the most computationally demanding part of the FMM algorithm, we take into consideration the effect of all the expansions in an interaction list of every single expansion we are trying to compute and perform the operation. This step by itself is a bit complicated to explain here, but I suppose you have the picture by now.

4- Now the second step of the downward pass: local-to-local shift operation. This is simply the segregation (a more descriptive word here might be: decomposition) of each parent into its children. This starts at the coarsest level and goes all the way down to the finest. Also one must be careful to add the M2L and L2L contribution to one another for each expansion in the same cube/partition.

5- Finally evaluation of the potential field is put into practice. This has two options: far-field potential evaluation and near-field potential evaluation. They depend on the location of the source points with respect to each of the target points.

This is merely a very simple overview of the translation theory utilized within the FMM. The sole aim of this explanation is to help beginners become more familiar with the details and to point them to the right track using relatively simple words. For more details, please check out the reference included in the original question above.