Next: Applications of FMM to Up: Fast multipole algorithm and Previous: Fast multipole algorithm

Estimation of the computational cost

We estimate the computational cost for Steps 3-6 since in FM-BIEM Steps 3-6 are iterated. Although we consider the two-dimensional case, we can similarly estimate the computational cost in three dimensions. The complexity for Step 6 is negligible because Steps 3-5 dominate the performance. For simplicity we carry out the estimation under the following conditions:
• Boundary elements are distributed uniformly.

• The number of unknowns is N.

• The number of boundary elements in a leaf is less than a fixed number M.

• The summation in the infinite series (2.3), (2.9), etc. is truncated at p terms.

From above conditions, the number of leaves is N/M, the depth of the quad-tree lf is and the total number of cells is . Notice that all leaves are assumed to be cells at level lf in this estimation.

• Cost of Step 3: In step 3 we compute multipole moments at leaves and translate multipole moments.
• Computation of multipole moments The number of leaves is N/M, the number of boundary elements is M in a leaf and the number of the multipole moments to be computed in a leaf is p. Therefore the cost for computation of multipole moments is O(pN).
• Translation of multipole moments The number of M2M translations via (2.7) at level is and the cost per translation is O(p2). We iterate these translations from to . Therefore the cost for M2M translations is .
• Cost of Step 4: In step 4 we compute coefficients of the local expansion and translate them.
• Computation of coefficients of the local expansion The number of M2L translations via (2.10) at level is and the cost per translation is O(p2). We iterate these translations from to . Therefore the cost for M2L translations is .

• Translation of coefficients of the local expansion The number of L2L translations via (2.12) at level is and the cost per translation is O(p2). We iterate these translations from to . Therefore the cost for L2L translations is
• Cost of Step 5: In step 5 we evaluate the contribution from adjacent cells at all the leaves with direct computation and the contribution from cells which are not adjacent with the local expansion at all the leaves.
• Evaluation with direct computation The number of leaves is N/M and the cost for the direct computation per leaf is O(9M2). Therefore the cost is O(9MN).
• Evaluation with the local expansion The number of leaves is N/M and the number of boundary elements is M in a leaf. Also, we truncate the infinite series (2.9) taking p terms. Therefore the cost is O(pN).
Hence the total computational complexity per iteration is

From above estimation one can see that the computational cost for M2L translation is expensive. Therefore, M2L translation is the bottleneck in FMM. To make matters worse, the cost for M2L translation is O(216p4N/M) in three dimensions, making the cost for M2L translation a more serious problem than in two dimensions.

Next: Applications of FMM to Up: Fast multipole algorithm and Previous: Fast multipole algorithm
Ken-ichi Yoshida
2001-07-28