Skip to main content
construction release_alert
Scholars@Duke will be undergoing maintenance April 11-15. Some features may be unavailable during this time.
cancel

Fast fourier transform accelerated fast multipole algorithm

Publication ,  Journal Article
Elliott, WD; Board, JA
Published in: SIAM Journal on Scientific Computing
January 1, 1996

This paper describes an O(p2 log2(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 O(p4N), 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(p4) 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 O(p2 log2(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.

Duke Scholars

Published In

SIAM Journal on Scientific Computing

DOI

ISSN

1064-8275

Publication Date

January 1, 1996

Volume

17

Issue

2

Start / End Page

398 / 415

Related Subject Headings

  • Numerical & Computational Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Elliott, W. D., & Board, J. A. (1996). Fast fourier transform accelerated fast multipole algorithm. SIAM Journal on Scientific Computing, 17(2), 398–415. https://doi.org/10.1137/S1064827594264259
Elliott, W. D., and J. A. Board. “Fast fourier transform accelerated fast multipole algorithm.” SIAM Journal on Scientific Computing 17, no. 2 (January 1, 1996): 398–415. https://doi.org/10.1137/S1064827594264259.
Elliott WD, Board JA. Fast fourier transform accelerated fast multipole algorithm. SIAM Journal on Scientific Computing. 1996 Jan 1;17(2):398–415.
Elliott, W. D., and J. A. Board. “Fast fourier transform accelerated fast multipole algorithm.” SIAM Journal on Scientific Computing, vol. 17, no. 2, Jan. 1996, pp. 398–415. Scopus, doi:10.1137/S1064827594264259.
Elliott WD, Board JA. Fast fourier transform accelerated fast multipole algorithm. SIAM Journal on Scientific Computing. 1996 Jan 1;17(2):398–415.

Published In

SIAM Journal on Scientific Computing

DOI

ISSN

1064-8275

Publication Date

January 1, 1996

Volume

17

Issue

2

Start / End Page

398 / 415

Related Subject Headings

  • Numerical & Computational Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics