next up previous contents
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: From above conditions, the number of leaves is N/M, the depth of the quad-tree lf is $\log_4 (N/M)$ and the total number of cells is $1 + 4 + 4^2 + \ldots + 4^{\log_4 (N/M)} = (4/3)(N/M-1) \approx
4N/(3M)$. Notice that all leaves are assumed to be cells at level lf in this estimation.

Hence the total computational complexity per iteration is

\begin{eqnarray*}O(p N) + O(4p^2N/3M) + O(36p^2N/M) + O(4p^2N/3M) + O(9 M N) +
O(p N) \approx O(N)
\end{eqnarray*}


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 up previous contents
Next: Applications of FMM to Up: Fast multipole algorithm and Previous: Fast multipole algorithm
Ken-ichi Yoshida
2001-07-28