next up previous contents
Next: Estimation of the computational Up: Fast multipole algorithm and Previous: Fast multipole algorithm and

Fast multipole algorithm

Step 1. Discretisation:

Discretise S in the same manner as in the conventional BIEM using boundary elements.

Step 2. Construction of quad-tree structure:

Consider a square which circumscribes S and call this square the cell of level 0. Now take a cell (a parent cell) of level l $(l \ge 0)$ and divide it into 4 equal sub squares whose edge length is half of that of the parent cell and call any of them a cell (a child cell) of level l+1 if some boundary elements belong to this square (See Fig.2.6). In this statement a boundary element is said to belong to a cell C if the centroid of the element is in C (See Fig.2.7). Stop the cell subdivision if the number of boundary elements belonging to the cell is smaller than a given number. A childless cell is called a leaf.

Step 3. Computation of the multipole moments (Upward):

First we compute the multipole moments associated with leaves using (2.4). Here the multipole moments associated with a cell C stand for the integrals in (2.4) with O taken as the centroid of C. For a non-leaf cell C of level l, we compute the multipole moments associated with C by adding all the multipole moments of C's children after shifting the origin from the centroids of C's children to that of C via (2.7) (See Fig.2.8). This procedure is repeated for $l\ge 2$ tracing the tree structure of cells upward (decreasing l).

Step 4. Computation of the coefficients of the local expansion (Downward):

We have to prepare some definitions first. We say that two cells are ``adjacent cells at level l'' if these cells are both of the level l and share at least one vertex. Two cells are said to be ``well-separated at level l'' if they are not adjacent at level l but their parent cells are adjacent at level l-1. The list of all the well-separated cells from a level l cell C is called the interaction list of C. The maximum number of well-separated cells is 62-32=27 (See Fig.2.9). Now we compute the local expansion associated with a cell C. The local expansion associated with C represents a sum of the contributions due to boundary elements in cells of the interaction list of C and the contributions due to all boundary elements in cells which are not adjacent to C's parent. The former is computed as we substitute the multipole moments associated with cells in the interaction list of C into (2.10) and the latter by translating the local expansion associated with C's parent via (2.12) as the centre of the local expansion is shifted from the centroid of C's parent ( $\mbox{\boldmath$\space x $ }_0$) to the centroid of C ( $\mbox{\boldmath$\space x $ }_1$) (See Fig.2.8). The sum of these contributions gives the local expansion associated with C. We repeat these procedures starting from l=2 and increasing l along the tree structure until we reach leaves. When l=2, the coefficients of the local expansion are computed only by using (2.10). This is because cells of level 1 have no well-separated cells.

Step 5. Evaluation of the integral in (2.1):

We now compute the right-hand side of (2.1). Let C be a cell of the level l to which the collocation point $\mbox{\boldmath$\space x $ }$ belongs, and let C' be a cell of level l adjacent to C. We compute the contribution from boundary elements in C' to the integral in (2.1) at collocation points in C directly if either C or C' is a leaf. When C is a leaf, we also compute the right-hand side of (2.9) using the coefficients of the local expansion associated with C. The sum of all these terms as l increases from 2 gives the integral in (2.1) evaluated at the collocation points of all boundary elements.

Step. 6 Update the candidate vector and go back to Step. 3.

Figs. 2.10-2.14 present examples to give definite pictures of FMM. Figs. 2.10-2.14 show procedures for the evaluation of contributions from all boundary elements to a certain observation point. Figs. 2.10-2.14 correspond to Steps 1-5, respectively, in the algorithm described above.
  
Figure 2.6: Construction of a tree structure and corresponding quad-tree
\begin{figure}
\begin{center}
\epsfile{file=FIG/tree_construct.eps,scale=0.7} \epsfile{file=FIG/tree.eps,scale=0.7} \end{center} \end{figure}


  
Figure 2.7: Boundary element is in a cell or not
\begin{figure}
\begin{center}
\epsfile{file=FIG/cell_in_leaf.eps,scale=1.0} \end{center} \end{figure}


  
Figure 2.8: M2M translation and L2L translation
\begin{figure}
\begin{center}
\epsfile{file=FIG/M2ML2L.eps,scale=0.6} \end{center} \end{figure}


  
Figure 2.9: Adjacent cells and well-separated cells
\begin{figure}
\begin{center}
\epsfile{file=FIG/M2L_rev.eps,scale=0.8} \end{center} \end{figure}


  
Figure 2.10: Discretisation (Step 1)
\begin{figure}
\begin{center}
\epsfile{file=FIG/uum0.eps,scale=0.6} \end{center} \end{figure}


  
Figure 2.11: Construction of tree structure (Step 2)
\begin{figure}
\begin{center}
\epsfile{file=FIG/uum1.eps,scale=0.6} \end{center} \end{figure}


  
Figure 2.12: Multipole moments and M2M translation (Step 3)
\begin{figure}
\begin{center}
\epsfile{file=FIG/uum2.eps,scale=0.6} \end{center} \end{figure}


  
Figure 2.13: M2L and L2L translation (Step 4)
\begin{figure}
\begin{center}
\epsfile{file=FIG/uum3.eps,scale=0.6} \end{center} \end{figure}


  
Figure 2.14: Evaluation of total contribution (Step 5)
\begin{figure}
\begin{center}
\epsfile{file=FIG/uum4.eps,scale=0.6} \end{center} \end{figure}


next up previous contents
Next: Estimation of the computational Up: Fast multipole algorithm and Previous: Fast multipole algorithm and
Ken-ichi Yoshida
2001-07-28