Fast Fourier Transform Accelerated Fast Multipole Algorithm
William D. Elliott, John A. Board · SIAM Journal on Scientific Computing · 1996
This paper describes an $\mathcal{O}(p^2 \log _2 (p)N)$ implementation of the fast multipole algorithm (FMA) for N-body simulations. This method of computing the FMA is faster than the original, which is $\mathcal{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 $\mathcal{O}(p^4 )$ computation in the original FMA is a convolution-like operation on a matrix of multipole coefficients. This paper describes the implementation details of a conversion of this limiting computation to linear convolution, which is then computed in the Fourier domain using the fast Fourier transform (FFT), based on a method originally outlined by Greengard and Rokhlin. In addition, this paper describes a new block decomposition of the multipole expansion data that provides numerical stability and efficient computation. The resulting $\mathcal{O}(p^2 \log _2 (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$.
Cited by 120 works. doi:10.1137/s1064827594264259
Authors
References
- A fast algorithm for particle simulations
- A hierarchical O(N log N) force-calculation algorithm
- The Rapid Evaluation of Potential Fields in Particle Systems
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- Implementing the fast multipole method in three dimensions
- Accelerated molecular dynamics simulation with the parallel fast multipole algorithm
- The rapid evaluation of potential fields in three dimensions
- The Parallel Multipole Method on the Connection Machine
- A parallel version of the fast multipole method
- The Numerical Solution of the N-Body Problem