RECFMM: Recursive Parallelization of the Adaptive Fast Multipole Method for Coulomb and Screened Coulomb Interactions
Year: 2016
Communications in Computational Physics, Vol. 20 (2016), Iss. 2 : pp. 534–550
Abstract
We present RECFMM, a program representation and implementation of a recursive scheme for parallelizing the adaptive fast multipole method (FMM) on shared-memory computers. It achieves remarkable high performance while maintaining mathematical clarity and flexibility. The parallelization scheme signifies the recursion feature that is intrinsic to the FMM but was not well exploited. The program modules of RECFMM constitute a map between numerical computation components and advanced architecture mechanisms. The mathematical structure is preserved and exploited, neither obscured nor compromised, by parallel rendition of the recursion scheme. Modern software system – CILK in particular, which provides graph-theoretic optimal scheduling in adaptation to the dynamics in parallel execution – is employed. RECFMM supports multiple algorithm variants that mark the major advances with low-frequency interaction kernels, and includes the asymmetrical version where the source particle ensemble is not necessarily the same as the target particle ensemble. We demonstrate parallel performance with Coulomb and screened Coulomb interactions.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/cicp.230216.140416sw
Communications in Computational Physics, Vol. 20 (2016), Iss. 2 : pp. 534–550
Published online: 2016-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 17
-
Fast multipole methods for approximating a function from sampling values
Liu, Guidong | Xiang, ShuhuangNumerical Algorithms, Vol. 76 (2017), Iss. 3 P.727
https://doi.org/10.1007/s11075-017-0279-z [Citations: 6] -
Fast computation of the spectral differentiation by the fast multipole method
Tian, Yan | Xiang, Shuhuang | Liu, GuidongComputers & Mathematics with Applications, Vol. 78 (2019), Iss. 1 P.240
https://doi.org/10.1016/j.camwa.2019.02.024 [Citations: 3] -
Fast electrostatic solvers for kinetic Monte Carlo simulations
Saunders, William Robert | Grant, James | Müller, Eike Hermann | Thompson, IanJournal of Computational Physics, Vol. 410 (2020), Iss. P.109379
https://doi.org/10.1016/j.jcp.2020.109379 [Citations: 7] -
Spaceland Embedding of Sparse Stochastic Graphs
Pitsianis, Nikos | Iliopoulos, Alexandros-Stavros | Floros, Dimitris | Sun, Xiaobai2019 IEEE High Performance Extreme Computing Conference (HPEC), (2019), P.1
https://doi.org/10.1109/HPEC.2019.8916505 [Citations: 4] -
A heterogeneous FMM for layered media Helmholtz equation I: Two layers inR2
Cho, Min Hyung | Huang, Jingfang | Chen, Dangxing | Cai, WeiJournal of Computational Physics, Vol. 369 (2018), Iss. P.237
https://doi.org/10.1016/j.jcp.2018.05.007 [Citations: 9] -
Hierarchical Orthogonal Matrix Generation and Matrix-Vector Multiplications in Rigid Body Simulations
Fang, Fuhui | Huang, Jingfang | Huber, Gary | McCammon, J. Andrew | Zhang, BoSIAM Journal on Scientific Computing, Vol. 40 (2018), Iss. 3 P.A1345
https://doi.org/10.1137/17M1117744 [Citations: 0] -
Scalable Hierarchical Multipole Methods Using an Asynchronous Many-Tasking Runtime System
DeBuhr, Jackson | Zhang, Bo | D'Alessandro, Luke2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), (2017), P.1226
https://doi.org/10.1109/IPDPSW.2017.88 [Citations: 0] -
Brief Announcement
Schardl, Tao B. | Lee, I-Ting Angelina | Leiserson, Charles E.Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, (2018), P.351
https://doi.org/10.1145/3210377.3210658 [Citations: 9]