Fast Fourier Transform Accelerated Fast Multipole Algorithm
William D. Elliott and
John A. Board, Jr.
Abstract
This paper describes an O(p^2 log (p)N) implementation of the Fast
Multipole Algorithm (FMA) for N-body simulations. This new method of
computing the FMA is faster than the original, which was O(p^4 N),
where p is the number of terms retained in the truncated multipole
expansion representation of the potential field of a collection of
charged particles. The p term determines the accuracy of the
calculation. The limiting O(p^ 4) computation in the original FMA is
a convolution-like operation on an array of multipole coefficients.
This paper describes a conversion of the limiting computation to
linear convolution which is then computed in the Fourier domain using
the Fast Fourier Transform (FFT). The resulting O(p^2 log (p))
subroutine has a speedup of 2 on a sequential processor over the
original method for p = 8, and a speedup of 4 for p = 16. The new
subroutine vectorizes well and has a speedup of 3 on a vector
processor at p = 8 and a speedup of 6 at p = 16.
Back to the Scientific Computions Group Home Page