Алгори́тм Ба́рнса — Ха́та, або моде́ль Ба́рнса — Ха́та (англ. Barnes–Hut simulation, TreeCode) — алгоритм для моделювання гравітаційної задачі N тіл у пласких структурах, подібних до галактик чи планетних систем.
Принцип роботи
Плаский простір поділяють на чотири прямокутні комірки. Якщо в якійсь із утворених комірок перебуває більше одного тіла, її, у свою чергу, рекурсивно поділяють на чотири комірки. Таким чином утворюється ієрархічна структура — дерево ступеня чотири (чотири-дерево, англ. quad-tree). Деякі з утворених таким чином комірок можуть бути порожніми. Взаємодію тіл у сусідніх комірках розглядають індивідуально, а тіла у віддалених комірках розглядають як одне велике тіло, розташоване в центрі мас, за рахунок чого досягається значне скорочення обчислень: (замість N*(N-1) обчислень потрібно виконати лише ).
Алгоритм застосовують для моделювання динамічних систем, в яких сила, що діє на кожний окремий елемент системи, може бути розрахована як суперпозиція сил від решти елементів, наприклад, при моделюванні поведінки магнітних рідин[].
Див. також
Джерела
- Tom Ventimiglia and Kevin Wayne (2003). . 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.
Посилання
- Treecodes, J. Barnes [ 2 квітня 2013 у Wayback Machine.]
- Parallel TreeCode [ 2 квітня 2013 у Wayback Machine.]
- PEPC — The Pretty Efficient Parallel Coulomb solver
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algori tm Ba rnsa Ha ta abo mode l Ba rnsa Ha ta angl Barnes Hut simulation TreeCode algoritm dlya modelyuvannya gravitacijnoyi zadachi N til u plaskih strukturah podibnih do galaktik chi planetnih sistem Pobudova modeli Barnsa Hata dlya sotni til Mezhi komirok obvedeno blakitnim Princip robotiPlaskij prostir podilyayut na chotiri pryamokutni komirki Yaksho v yakijs iz utvorenih komirok perebuvaye bilshe odnogo tila yiyi u svoyu chergu rekursivno podilyayut na chotiri komirki Takim chinom utvoryuyetsya iyerarhichna struktura derevo stupenya chotiri chotiri derevo angl quad tree Deyaki z utvorenih takim chinom komirok mozhut buti porozhnimi Vzayemodiyu til u susidnih komirkah rozglyadayut individualno a tila u viddalenih komirkah rozglyadayut yak odne velike tilo roztashovane v centri mas za rahunok chogo dosyagayetsya znachne skorochennya obchislen zamist N N 1 obchislen potribno vikonati lishe O N log N displaystyle O N log N Algoritm zastosovuyut dlya modelyuvannya dinamichnih sistem v yakih sila sho diye na kozhnij okremij element sistemi mozhe buti rozrahovana yak superpoziciya sil vid reshti elementiv napriklad pri modelyuvanni povedinki magnitnih ridin dzherelo Div takozhZadacha dvoh til Zadacha troh til Gravitacijna zadacha N tilDzherelaTom Ventimiglia and Kevin Wayne 2003 Princeton University Computer Science COS 126 Arhiv originalu za 11 travnya 2021 Procitovano 25 sichnya 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 Arhiv originalu za 22 lipnya 2013 Procitovano 30 bereznya 2012 PosilannyaTreecodes J Barnes 2 kvitnya 2013 u Wayback Machine Parallel TreeCode 2 kvitnya 2013 u Wayback Machine PEPC The Pretty Efficient Parallel Coulomb solver