On the Efficient Implementation of the Fast Multipole Algorithm.
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The Fast Multipole Method FMM is a recently developed algorithm for the evaluation of potential fields in particle systems. In order to evaluate the fields induced by a set of N charges or masses on each other, the FMM requires order ON work rather than the ON squared work required by the direct evaluation of pairwise interactions. The constant of proportionality for the method depends on the cost of applying a translation operator to a multiple or Taylor expansion. In existing implementations, this is Op squared in two dimensions and Op to the 4th power in three, where p is the degree of the expansion. In this paper we describe a procedure permitting translation operators to be applied to p to the 4th power degree expansions for a cost proportional to p.log p in two dimensions, and p squared. log p in three. The incorporation of this technique into the FMM scheme speeds up the execution of two-dimensional single precision codes by a factor of two or three, and the execution of three-dimensional codes by roughly a factor of eight.
- Numerical Mathematics
- Nuclear Physics and Elementary Particle Physics