Effective Implementation of the Fast Multipole Method for Particle Interaction with Newtonian Potential
https://doi.org/10.15514/ISPRAS-2023-35(6)-14
Abstract
We consider rotation-based fast multipole method for the Laplace equation and its application in cases where particle interactions are governed by the Biot—Savart law. The paper presents the necessary formulas for algorithm implementation and addresses less frequently discussed topics, such as the normalization of spherical harmonics and the associated Wigner matrices normalization. The main focus of the paper is devoted to describing the details of the software implementation that significantly accelerate the performance of the code both on CPU and GPU (using CUDA technology). We provide a comprehensive explanation of proposed techniques and include code examples. We have implemented a C++ program using these methods and conducted a comparative analysis with open-source implementations of the fast multipole method, confirming the high efficiency of our approach.
About the Author
Viktor Mikhailovich AUSHEV
Bauman Moscow State Technical University
Russian Federation
Russian Federation
Master's student of Applied Mathematics department. Research interests: fast methods, high performance computing, numerical methods of electrodynamics, finite element method, numerical methods of linear algebra.
References
1. J. Barnes, P. Hut. A hierarchical O(NlogN) force-calculation algorithm. // Nature. 1986. Vol. 324. P. 446–449. DOI: 10.1038/324446a0.
2. K. Nabors, J. White. FastCap: A multipole-accelerated 3-D capacitance extraction program // IEEE Transactions on Computer-Aided Design. 1991. Vol. 10. P. 1447–1459.
3. M. Kamon, M. J. Tsuk, J. K. White. FASTHENRY: a multipole-accelerated 3-D inductance extraction program. // IEEE Transactions on Microwave Theory and Techniques. 1994. Vol. 42, № 9. P. 1750–1758.
4. L. Greengard, M.C. Kropinski, A. Mayo. Integral equation methods for stokes flow and isotropic elasticity in the plane. // J. Comput. Physics. 1996. Vol. 125, № 2. P. 403–414.
5. DOI: 10.1006/jcph.1996.0102
6. A.-K. Tornberg, L. Greengard. A fast multipole method for the three-dimensional Stokes equations. // Journal of Computational Physics. 2008. Vol 227, № 3. P. 1613–1619. DOI: 10.1016/j.jcp.2007.06.029
7. L. Greengard, V. Rokhlin. A fast algorithm for particle simulations. // J. Comput. Phys. 1987. Vol. 73, № 2. P. 325–348. DOI: 10.1016/0021-9991(87)90140-9
8. H. Cheng, L. Greengard, V. Rokhlin. A fast adaptive multipole algorithm in three dimensions. // J. Comput. Phys. 1999. Vol. 155. P. 468–498. DOI: 10.1006/jcph.1999.6355
9. M. A. Epton, B. Dembart. Multipole translation theory for the three-dimensional Laplace and Helmholtz equations. // SIAM J. on Scientific Computing. 1995. Vol. 16, №4. P. 865–897. DOI: 10.1137/0916051
10. R. Beatson, L. Greengard. A short course on fast multipole methods. // Wavelets, Multilevel methods and Elliptic PDEs. 1997. P. 1–37.
11. J. Makino. Yet another fast multipole method without multipoles — pseudoparticle multipole method. // J. Comput. Phys. 1999. Vol. 151, № 2. P. 910–920.
12. A. Kawai, J. Makino. A simple formulation of the fast multipole method: pseudo-particle multipole method. // SIAM Conference on Parallel Processing for Scientific Computing. 1998. DOI: 10.48550/arXiv.astro-ph/9812431
13. N.Y. Gnedin. Hierarchical Particle Mesh: An FFT-accelerated fast multipole method. // The Astrophysical Journal Supplement Series. 2019. Vol. 243, № 2. 19 p. DOI: 10.3847/1538-4365/ab2d24
14. C.R. Anderson. An implementation of the fast multipole method without multipoles. // SIAM J. on Scientific and Statistical Computing. 1992. Vol. 13. P. 923–947. DOI: 10.1137/0913055
15. R. Yokota, L.A. Barba. Treecode and fast multipole method for N-Body simulation with CUDA. // GPU Computing Gems. Emerald Edition. Boston: Elsevier and Morgan Kaufmann, 2011. P. 113–132. DOI: 10.1016/B978-0-12-384988-5.00009-7
16. B. Bramas. (2020). TBFMM: A C++ generic and parallel fast multipole method library. // Journal of Open Source Software. 2020. Vol. 5, № 56. P. 2444–2453. DOI: 10.21105/joss.02444
17. Z. Gimbutas, L. Greengard. Computational Software: Simple FMM Libraries for Electrostatics, Slow Viscous Flow, and Frequency-Domain Wave Propagation. // Communications in Computational Physics. 2015. Vol. 18, № 2. 516–528. DOI: 10.4208/cicp.150215.260615sw
18. T. Wang, R. Yokota, L.A. Barba. ExaFMM: a high-performance fast multipole method library with C++ and Python interfaces. // Journal of Open Source Software. 2021. Vol. 6, № 61. P. 3145–3149. DOI: 10.21105/joss.03145
19. P. Blanchard, B. Bramas, O. Coulaud, et al. ScalFMM: A Generic Parallel Fast Multipole Library. // SIAM Conference on Computational Science and Engineering. 2015.
20. E.O. Steinborn, K. Ruedenberg. Rotation and translation of regular and irregular solid spherical harmonics. // Advances in Quantum Chemistry. 1973. Vol. 7. P. 1–81.
21. L. Biedenharn, J. Louck, P. Carruthers. Angular momentum in quantum physics: Theory and Application. Cambridge: Cambridge University Press, 1984. 716 p.
22. Abramowitz M., Stegun I.A. Handbook of mathematical functions. New York: Dover, 1965. 1046 p.
23. L. Greengard, V. Rokhlin. A new version of the fast multipole method for the Laplace equation in three dimensions. // Acta Numerica. 1997. Vol. 6. P. 229–269. DOI: 10.1017/S0962492900002725
24. E. Wigner. Group theory and its application to the quantum mechanics of atomic spectra. New York: Academic Press, 1959. 384 p. DOI: 10.1017/S0013091500025220
25. H. Dachsel. Fast and accurate determination of the Wigner rotation matrices in the fast multipole method. // J. Chem. Phys. 2006. Vol. 124. P. 144115–144121. DOI: 10.1063/1.2194548
26. Z. Gimbutas, L. Greengard. A fast and stable method for rotating spherical harmonic expansions. J. Comput. Phys. 2009. Vol. 228, № 16. P. 5621-5627. DOI: 10.1016/j.jcp.2009.05.014
Review
For citations:
AUSHEV V.M. Effective Implementation of the Fast Multipole Method for Particle Interaction with Newtonian Potential. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2023;35(6):213-234. (In Russ.) https://doi.org/10.15514/ISPRAS-2023-35(6)-14
Email this article 