We have implemented the fast multipole method (FMM) on a special-purpose computer
GRAPE (GRAvity piPE). The FMM is one of the fastest approximate algorithms to
calculate forces among particles. Its calculation cost scales as
O(N), while the naive algorithm scales as
O(N
2). Here, N is the number of particles
in the system. GRAPE is hardware dedicated to the calculation of Coulombic or
gravitational forces among particles. GRAPE's calculation speed is
100—1000 times faster than that of conventional computers of the same
price, though it cannot handle anything but force calculation. We can expect
significant speedup by the combination of the fast algorithm and the fast hardware.
However, a straightforward implementation of the algorithm actually runs on GRAPE at
rather modest speed. This is because of the limited functionality of the hardware.
Since GRAPE can handle particle forces only, just a small fraction of the overall
calculation procedure can be put on it. The remaining part must be performed on a
conventional computer connected to GRAPE. In order to take full advantage of the
dedicated hardware, we modified the FMM using the pseudoparticle multipole method
and Anderson's method. In the modified algorithm, multipole and local expansions are
expressed by distribution of a small number of imaginary particles
(pseudoparticles), and thus they can be evaluated by GRAPE. Results of numerical
experiments on ordinary GRAPE systems show that, for large-N systems
(N ≥ 105), GRAPE accelerates the FMM by a factor
ranging from 3 for low accuracy (RMS relative force error
~10—2) to 60 for high accuracy (RMS relative force error
~10— 5). Performance of the FMM on GRAPE exceeds that of
Barnes—Hut treecode on GRAPE at high accuracy, in case of
close-to-uniform distribution of particles. However, in the same experimental
environment the treecode outperforms the FMM for inhomogeneous distribution of
particles.
