Next: New FMM Up: Original FMM Previous: Formulation for original FMM

## Algorithm for original FMM

The algorithm of the original FMM is described as follows:

Step 1. Discretisation: Discretise S in the same manner as in the conventional BIEM.
Step 2. Determination of octtree structure: Consider a cube which circumscribes S and call this cube the cell of level 0. Now take a cell (a parent cell) of level l and divide it into 8 equal sub cubes whose edge length is half of that of the parent cell and call any of them which contains some boundary elements a cell of level l+1. Continue the subdivision of cells until the number of boundary elements in the cell is below a given number. A cell having no children is called a leaf.
Step 3. Computation of the multipole moments:

First compute the multipole moments associated with leaves via (14) and (15) taking the centre (O) of the multipole moment as the centroid of C. Now consider a non-leaf cell C of level l. We compute the multipole moments associated with C by translating the multipole moments of C's children via (16) and (17) with the origin shifted from the centroids of C's children (O) to that of C (O') and adding all the translated multipole moments of C's children. We repeat this procedure tracing the tree structure of cells upward (decreasing l) until we reach level 2 cells.

Step 4. Computation of the local expansion:

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. Now we compute the local expansion associated with a cell C. The local expansion associated with C represents a sum of the contribution due to boundary elements in cells of the interaction list of C and the contribution due to all boundary elements in cells which are not adjacent to C's parent. The former is computed by substituting the multipole moments associated with cells of the interaction list of C to (19) and (20) and the latter by translating the local expansion associated with C's parent via (21) and (22) as the centre of the local expansion is shifted from the centroid of C's parent ( ) to the centroid of C ( ). 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 (19) and (20). This is because cells of level 1 have no well-separated cells.

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

We now compute the integral in (5) at leaves (denoted by C). First we compute the contribution from boundary elements in cells adjacent to C using (6) in the same manner as in the conventional BIEM and then compute the contribution from cells which are not adjacent to C using (18). The sum of these contributions describes the contribution from all boundary elements.

Next: New FMM Up: Original FMM Previous: Formulation for original FMM
Ken-ichi Yoshida
2001-03-26