** Next:** Panel clustering method
** Up:** Brief history of FMM
** Previous:** Fast Multipole 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*(*N*^{2}) to *O*(*N*), whereas tree method to
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
,
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:** Panel clustering method
** Up:** Brief history of FMM
** Previous:** Fast Multipole Method
*Ken-ichi Yoshida*

*2001-07-28*