Алгоритм Барнса — Хата
Алгори́тм Ба́рнса — Ха́та, або моде́ль Ба́рнса — Ха́та (англ. Barnes–Hut simulation, TreeCode) — алгоритм для моделювання гравітаційної задачі N тіл у пласких структурах, подібних до галактик чи планетних систем.
Принцип роботи[ред. | ред. код]
Плаский простір поділяють на чотири прямокутні комірки. Якщо в якійсь із утворених комірок перебуває більше одного тіла, її, у свою чергу, рекурсивно поділяють на чотири комірки. Таким чином утворюється ієрархічна структура — дерево ступеня чотири (чотири-дерево, англ. quad-tree). Деякі з утворених таким чином комірок можуть бути порожніми[1]. Взаємодію тіл у сусідніх комірках розглядають індивідуально, а тіла у віддалених комірках розглядають як одне велике тіло, розташоване в центрі мас, за рахунок чого досягається значне скорочення обчислень: (замість N*(N-1) обчислень потрібно виконати лише )[2].
Алгоритм застосовують для моделювання динамічних систем, в яких сила, що діє на кожний окремий елемент системи, може бути розрахована як суперпозиція сил від решти елементів, наприклад, при моделюванні поведінки магнітних рідин[джерело?].
Див. також[ред. | ред. код]
Джерела[ред. | ред. код]
- ↑ Tom Ventimiglia and Kevin Wayne (2003). Programming Assignment: Barnes-Hut Galaxy Simulator. Princeton University: Computer Science: COS 126. Архів оригіналу за 11 травня 2021. Процитовано 25 січня 2021.
- ↑ 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.
- 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.