Алгоритм Барнса — Хата

Побудова моделі Барнса—Хата для сотні тіл. Межі комірок обведено блакитним.

Алгори́тм Ба́рнса — Ха́та, або моде́ль Ба́рнса — Ха́та (англ. Barnes–Hut simulation, TreeCode) — алгоритм для моделювання гравітаційної задачі N тіл у пласких структурах, подібних до галактик чи планетних систем.

Принцип роботи

Плаский простір поділяють на чотири прямокутні комірки. Якщо в якійсь із утворених комірок перебуває більше одного тіла, її, у свою чергу, рекурсивно поділяють на чотири комірки. Таким чином утворюється ієрархічна структура — дерево ступеня чотири (чотири-дерево, англ. quad-tree). Деякі з утворених таким чином комірок можуть бути порожніми[1]. Взаємодію тіл у сусідніх комірках розглядають індивідуально, а тіла у віддалених комірках розглядають як одне велике тіло, розташоване в центрі мас, за рахунок чого досягається значне скорочення обчислень: (замість N*(N-1) обчислень потрібно виконати лише )[2].

Алгоритм застосовують для моделювання динамічних систем, в яких сила, що діє на кожний окремий елемент системи, може бути розрахована як суперпозиція сил від решти елементів, наприклад, при моделюванні поведінки магнітних рідин[3]. В цьому випадку необхідне розширення методу до тривімирного простору (Евклідового) з використанням дерева октантів.[4]

Див. також

Джерела

  1. ↑ Tom Ventimiglia and Kevin Wayne (2003). Programming Assignment: Barnes-Hut Galaxy Simulator. Princeton University: Computer Science: COS 126. Архів оригіналу за 11 травня 2021. Процитовано 25 січня 2021.
  2. ↑ J. Barnes and P. Hut (December 1986). A hierarchical O(N log N) force-calculation algorithm. Nature. 324 (4): 446—449. doi:10.1038/324446a0.
  3. ↑ Bogdan Tanygin (2019). Langevin dynamics simulation with dipole-dipole interactions: Massive performance improvements and advanced analytical integrator. Computer Physics Communications. 235: 169—178. doi:10.1016/j.cpc.2018.09.006.
  4. ↑ Polyakov, A. Yu.; Lyutyy, T. V.; Denisov, S.; Reva, V. V.; Hänggi, P. (1 червня 2013). Large-scale ferrofluid simulations on graphics processing units. Computer Physics Communications. Т. 184, № 6. с. 1483—1489. doi:10.1016/j.cpc.2013.01.016. ISSN 0010-4655. Процитовано 4 листопада 2024.

Література

  • J. Dubinski (October 1996). A Parallel Tree Code. New Astronomy. 1 (2): 133—147. doi:10.1016/S1384-1076(96)00009-7. arXiv:astro-ph/9603097v1.
  • U. Becciani, R. Ansalonib, V. Antonuccio-Delogua, G. Erbaccic, M. Gamberaa, and A. Pagliarod (October 1997). A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system. Computer Physics Communications. 106 (1–2): 105—113. doi:10.1016/S0010-4655(97)00102-1.
  • T. Ventimiglia, and K. Wayne. The Barnes-Hut Algorithm. Архів оригіналу за 22 липня 2013. Процитовано 30 березня 2012.

Посилання