.png){kind=icon}
Return
Fast Fourier transform accelerated fast multipole algorithm
.png){kind=icon}
PRE
AI
DOI：10.1137/S1064827594264259.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper describes an 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 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 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(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.
Keywords:
N-body problem
many-body problem
fast multipole algorithm
fast multipole method
tree codes
molecular dynamics
fast Fourier transform
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
Organization
No organization information available
Cited Papers
Track Condition Analyser: Identification of Rail Rolling Surface Defects, Likely to Generate Fatigue Damage in Wheels, Using Instrumented Wheelset Measurements.png)
Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit
Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid TransitIF0
PREAI
ShareSave
ShareSave
View more