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