Эффективная реализация быстрого метода мультиполей для взаимодействия частиц с ньютоновским потенциалом
https://doi.org/10.15514/ISPRAS-2023-35(6)-14
Аннотация
В работе рассматривается быстрый метод мультиполей с использованием матриц поворота для операторов трансляции для расчета взаимодействия частиц с нютоновским потенциалом, а также его приложение для случая, когда взаимодействие между частицами описывается законом Био—Савара. В работе приведены формулы, необходимые для реализации алгоритма, а также такие редко затрагиваемые моменты, как нормировка сферических гармоник и связанная с ней нормировка матриц Вигнера. Основное внимание в работе уделено описанию деталей программной реализации, которые позволяют существенно ускорить работу кода, как для CPU, так и для GPU (с использованием технологии CUDA). Приведено подробное изложение предлагаемых методик, а также иллюстрирующие их листинги кода. С их использованием был реализован программный комплекс на C++ и проведено сравнение с открытыми программными реализациями быстрого метода мультиполей. Данное сравнение подтверждает высокую эффективность предложенной реализации.
Ключевые слова
Об авторе
Виктор Михайлович АУШЕВ
Московский государственный технический университет имени Н.Э. Баумана
Россия
Россия
Студент магистратуры кафедры “Прикладная математика”. Сфера научных интересов: быстрые методы, высокопроизводительные вычисления, численные методы электродинамики, метод конечных элементов, численные методы линейной алгебры.
Список литературы
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
Рецензия
Для цитирования:
АУШЕВ В.М. Эффективная реализация быстрого метода мультиполей для взаимодействия частиц с ньютоновским потенциалом. Труды Института системного программирования РАН. 2023;35(6):213-234. https://doi.org/10.15514/ISPRAS-2023-35(6)-14
For citation:
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
Послать статью по эл. почте 