Pseudoparticle Multipole Method: A Simple Method to Implement   High-Accuracy Treecode
  In this letter we describe the pseudoparticle multipole method (P2M2), a new method to express multipole expansion by a distribution of pseudoparticles. We can use this distribution of particles to calculate high order terms in both the Barnes-Hut treecode and FMM. The primary advantage of P2M2 is that it works on GRAPE. GRAPE is a special-purpose hardware for the calculation of gravitational force between particles. Although the treecode has been implemented on GRAPE, we could handle terms only up to dipole, since GRAPE can calculate forces from point-mass particles only. Thus the calculation cost grows quickly when high accuracy is required. With P2M2, the multipole expansion is expressed by particles, and thus GRAPE can calculate high order terms. Using P2M2, we implemented an arbitrary-order treecode on GRAPE-4. Timing result shows GRAPE-4 accelerates the calculation by a factor between 10 (for low accuracy) to 150 (for high accuracy). Even on general-purpose programmable computers, our method offers the advantage that the mathematical formulae and therefore the actual program is much simpler than that of the direct implementation of multipole expansion. 
Atsushi Kawai (Institute of Physical and Chemical Research) and   Junichiro Makino (University of Tokyo)