next up previous contents
Next: Panel clustering method Up: Brief history of FMM Previous: Fast Multipole Method

Tree Method

Although Rokhlin and Greengard have developed FMM, they were not the only researchers to make efforts to reduce the computational cost for BIEM and N-body problems. Tree method was investigated by Appel[3] and Barnes and Hut[4] in astrophysics. Appel represents Coulombic potentials due to distant particles with monopoles (if one needs more accurate result one may use quadruples, octuples.... in addition to monopoles), by taking a mass centre of two particles as their representative point (pseudoparticle) and continuing these hierarchical representations of particles recursively to build up a binary tree structure (See Fig.2.4). A pseudoparticle represents contributions from all descendants. Barnes and Hut refined Appel's work using a quad-tree in two dimensions and an oct-tree in three dimensions.

Tree method and FMM are the same in that both methods use multipole moments. FMM can reduce the computational cost for the pairwise force calculation from O(N2) to O(N), whereas tree method to $O(N \log
N)$ where N is the number of particles. This difference comes from the fact that FMM achieves further reduction by introducing the local expansion. Tree method can also be applied to BIEM. Indeed, Fukui and Katsumoto[25] applied FMM and Barnes and Hut algorithm to BIEM for two-dimensional Helmholtz's equation. Though FMM is superior to tree method in the estimated computational cost as $N \rightarrow
\infty$, tree method seems to be more popular in astrophysics because of its simple implementation. Indeed, overheads caused by introducing the local expansion are not negligible occasionally.



 
next up previous contents
Next: Panel clustering method Up: Brief history of FMM Previous: Fast Multipole Method
Ken-ichi Yoshida
2001-07-28