I overview the Fast Multipole Method (FMM) and the Barnes-Hut tree
method. These algorithms evaluate mutual gravitational interaction
between **N** particles in or times, respectively.
I present basic algorithms as well as recent developments, such as
Anderson's method of using Poisson's formula, the use of FFT, and
other optimization techniques. I also summarize the current states of
two algorithms. Though FMM with scaling is theoretically
preferred over tree method, comparisons of existing
implementations proved otherwize. This result is not surprizing, since
the calcultion cost of FMM scales as where **p** is the order
of expansion, while that of the tree method scales as .

Tue Sep 1 21:46:06 JST 1998