On the Efficient Implementation of the Fast Multipole Algorithm.
Abstract
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 O(N) work rather than the O(N 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 O(p squared) in two dimensions and O(p 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1988
- Accession Number
- ADA191167
Entities
People
- L. Greengard
- Vladimir Rokhlin
Organizations
- Yale University