next up previous contents
Next: Crack problems for three-dimensional Up: Applications of Fast Multipole Previous: Concluding remarks

Applications of the new FMM to three-dimensional problems

In this chapter we apply new Fast Multipole Boundary Integral Equation Method (new FM-BIEM) to crack problems for three-dimensional Laplace's equation and three-dimensional elastostatics. We compare the results obtained with the new FMM with those obtained in chapter 3. We shall call the FM-BIEM described in chapter 3 the ``original FM-BIEM'' to distinguish the ``FM-BIEM'' from the ``new FM-BIEM'' clearly. The new FMM provides techniques to reduce the computational cost for M2L translation which is the bottleneck in the original FMM. We achieve reduction of the computational cost by replacing procedures for M2L translation in the original FM-BIEM obtained in the chapter 3 with three procedures called M2X, X2X and X2L translations (details of M2X, X2X and X2L are given later).


  
Figure 4.1: Computational cost for M2L and M2X+X2X+X2L
\begin{figure}
\begin{center}
\leavevmode
\epsfile{file=FIG/NEWFMM:Lap3D/cost.eps,scale=0.7}\end{center}\end{figure}

Here we briefly describe the outline of the new FMM (See Greengard and Rokhlin[36] for more details). In the original FMM in three dimensions, if one truncates the infinite series in the multipole expansion taking p terms then the computational costs for M2M, M2L and L2L translations are proportional to O(p4), O(189p4)in the worst case and O(p4), respectively. In particular, M2L translation deteriorates the performance of FMM in dealing with three-dimensional problems where boundary elements are distributed densely. In order to reduce the cost for M2M, M2L and L2L translations, Greengard and Rokhlin proposed the new FMM on the basis of an integral representation for a fundamental solution. In this chapter we use techniques to reduce the computational cost for M2L translation because the complexity for M2L translation is dominant in FMM. In the new FMM we use the exponential expansion besides the multipole expansion and the local expansion. The M2X, X2X and X2L translation formulae are to convert the multipole expansion to the exponential expansion, the exponential expansion to another exponential expansion and the exponential expansion to the local expansion, respectively. The total computational costs for M2X, X2X and X2L translations are O(p3), O(p2) and O(p3), respectively, and therefore the total cost is O(p3) (See Fig.4.1). This is why the new FMM is more efficient than the original FMM.

 
next up previous contents
Next: Crack problems for three-dimensional Up: Applications of Fast Multipole Previous: Concluding remarks
Ken-ichi Yoshida
2001-07-28