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.