Accession Number : ADA191167

Title :   On the Efficient Implementation of the Fast Multipole Algorithm.

Descriptive Note : Research rept.,

Corporate Author : YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s) : Greengard, L ; Rokhlin, V

PDF Url : ADA191167

Report Date : Feb 1988

Pagination or Media Count : 20

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.

Descriptors :   *ALGORITHMS, *MULTIPOLARITY, *PARTICLES, *POTENTIAL THEORY, CODING, COSTS, EXPANSION, PRECISION, TEST AND EVALUATION, THREE DIMENSIONAL, TRANSLATIONS, TWO DIMENSIONAL, VELOCITY, APPLIED MATHEMATICS, FLUID DYNAMICS

Subject Categories : Numerical Mathematics
      Nuclear Physics & Elementary Particle Physics

Distribution Statement : APPROVED FOR PUBLIC RELEASE