next up previous contents
Next: Tree Method Up: Brief history of FMM Previous: Brief history of FMM

Fast Multipole Method

FMM was initially introduced by Rokhlin[69] as a fast solution method for integral equations for two-dimensional Laplace's equation. In Rokhlin's paper [69] the term ``FMM'' did not appear but the main framework of FMM was constructed. After Rokhlin's work, Greengard[33,35] refined the algorithm, applied FMM to two and three-dimensional N-body problems with Coulombic potential and showed the applicability of FMM to various fields. Rokhlin uses FMM in conjunction with an iterative solver to reduce the computational complexity for the matrix-vector multiplication from O(N2) to O(N). In FMM Rokhlin uses multipole moments to represent distant particle groups (particle means collocation point of a boundary element in BIEM) and introduces a local expansion to evaluate the contribution from distant particles in the form of a series. The multipole moment associated with a distant group can be translated into the coefficient of the local expansion associated with a local group. In addition to Rokhlin's work, Greengard introduces the hierarchical decomposition of a spatial domain with a quad-tree in two dimensions and an oct-tree in three dimensions to carry out efficient and systematic grouping of particles with tree structures. Greengard uses FMM to reduce the computational cost for the pairwise force calculation from O(N2) to O(N) (See Fig.2.1-2.3). In the last decades FMM has been applied to various fields such as BIEM, molecular dynamics (MD) (e.g. [81,8,15,14,48]). The fact that FMM was nominated as one of the top 10 algorithms of the century along with Fast Fourier Transform (FFT), QR algorithm, etc. in [7] shows how much influence it had on numerical analyses.

Applications of FMM to BIEM are investigated by many authors: by Fukui and Hattori [23] and Miyakoshi et al.[60] to two-dimensional Laplace's equation, by Fukui and Mochida[28] and Helsing[42] to two-dimensional elastostatics, by Nishimura et al.[65] and Nishida and Hayami[62] to three-dimensional Laplace's equation, by Yoshida et al.[84,87], Takahashi et al.[78], Fukui and Kutsumi[27] and Fu et al.[18,19] to three-dimensional elastostatics, by Chew et al.[10], Fujiwara[21] and Iritani et al.[47] to two-dimensional elastodynamics, by Fujiwara[22] and Yoshida et al.[86] to three-dimensional elastodynamics, and by Gomez and Power[30,31], Mammoli and Ingber[57,58], Fu and Rodin[20] and Takahashi et al.[79] to fluid mechanics. BIEM are particularly suitable for wave analyses in the infinite domain. Because of this advantage, applications of FM-BIEM to large-scale wave problems, particularly to acoustical and electromagnetic scattering problems, are vigorously investigated by many researchers: by Rokhlin[70], Lu and Chew[54,55], Song and Chew[77], Fukui and Katsumoto[25] and Yoshida et al.[85].

Recently several techniques to enhance the efficiencies of FMM are proposed by several authors. Rokhlin[70,71,72] proposed such a technique called the ``diagonal form''. We shall call this technique ``Rokhlin's diagonal form''. Epton and Dembart[17] and Elliot and Board[16] also proposed similar techniques. However, Rokhlin's diagonal form is known to have numerical instabilities in dealing with static problems and low frequency problems. Hence, Greengard et al.[36,11,34] and Hrycak and Rokhlin[44] proposed techniques based on the integral representation of a fundamental solution. In this thesis we call their techniques the ``new FMM''. The new FMM resolves problems of Rokhlin's diagonal form. Besides above techniques, several other techniques to improve the efficiency are proposed by White and Head-Gordon[82], Hu et al.[45], etc.

Applications of these techniques to FM-BIEM are found in several papers mentioned above, Koc and Chew[50], Hu et al.[46], Gyure and Stalzer[37], Dembart and Yip[13], Fukui and Katsumoto[26], Nishimura et al.[64] and Yoshida et al.[88,89]

  
Figure 2.1: Conventional evaluation of contribution from distant particles: O(N2) algorithm
\begin{figure}
\begin{center}
\epsfile{file=FIG/distant.eps,scale=0.7} \end{center} \end{figure}


  
Figure 2.2: Multipole moment represents distant particles
\begin{figure}
\begin{center}
\epsfile{file=FIG/distant2.eps,scale=0.7} \end{center} \end{figure}


  
Figure 2.3: Evaluation with the multipole moment and the local expansion: O(N) algorithm
\begin{figure}
\begin{center}
\epsfile{file=FIG/distant3.eps,scale=0.7} \end{center} \end{figure}


  
Figure 2.4: Particles and the corresponding binary tree
\begin{figure}
\begin{center}
\epsfile{file=FIG/bi_tree.eps,scale=0.7} \end{center} \end{figure}


next up previous contents
Next: Tree Method Up: Brief history of FMM Previous: Brief history of FMM
Ken-ichi Yoshida
2001-07-28