The tree algorithms [2,3] are now widely used in astrophysical community. For astrophysical simulations, the tree algorithms are particularly suitable because of the adaptive nature of the algorithm.

However, the use of tree algorithms in astrophysics has been limited to problems with relatively short timescales, such as collisions of two galaxies or large scale structure formation of the universe. This is mainly because of the high calculation cost associated with high-accuracy calculation. Existing implementations of Barnes-Hut treecode use only up to quadrupole moment. Therefore the calculation cost rises rather quickly when high accuracy is required.

As in the case of the fast multipole method (FMM) [6], it is possible to implement higher order multipole expansion to achieve high accuracy. However, the translation formulae for multipole expansion are rather complex and difficult to program.

In this paper, we describe a new method of implementing FMM or tree method with high order multipole expansion. The basic idea is extremely simple. In the multipole expansion, we approximate the potential field generated by a clump of particles by multipole expansion. We approximate the potential field back again by a distribution of particles. This approximation offers many advantages over traditional FMM which uses the coefficients of multipole expansion themselves. In this paper we describe the basic idea and formulae in two and three dimensions, and discuss the relation between the proposed method, traditional FMM, and Anderson's method [1] which is closely related to the the proposed method.

This paper is organized as follows. In section 2, the basic structure of the tree algorithm and FMM are summarized. In section 3, the mathematics of the new method is presented in two and three dimensions. In section 4, the result of some numerical tests for the truncation error is presented. Section 5 is for discussions and section 6 sums up.

Tue Feb 16 23:27:09 JST 1999