Acceleration of fast multipole method using special-purpose computer GRAPE

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(N2). Here, N is the number of particles in the system. GRAPE is hardware ded-icated 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 straightfor-ward implementation of the algorithm actually runs on GRAPE at rather modest speed. This is because of the lim