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

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

Алгори́тм Ба́рнса — Ха́та, або моде́ль Ба́рнса — Ха́та (Шаблон:Lang-en, Шаблон:Lang) — алгоритм для моделювання гравітаційної задачі N тіл у пласких структурах, подібних до галактик чи планетних систем.

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

Плаский простір поділяють на чотири прямокутні комірки. Якщо в якійсь із утворених комірок перебуває більше одного тіла, її, у свою чергу, рекурсивно поділяють на чотири комірки. Таким чином утворюється ієрархічна структура — дерево ступеня чотири (чотири-дерево, Шаблон:Lang-en). Деякі з утворених таким чином комірок можуть бути порожніми. Взаємодію тіл у сусідніх комірках розглядають індивідуально, а тіла у віддалених комірках розглядають як одне велике тіло, розташоване в центрі мас, за рахунок чого досягається значне скорочення обчислень: (замість N*(N-1) обчислень потрібно виконати лише $O(N\log N)$).

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

Див. також

• Задача двох тіл
• Задача трьох тіл
• Гравітаційна задача N тіл

Література

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite web

Посилання

• Treecodes, J. Barnes Шаблон:Webarchive
• Parallel TreeCode Шаблон:Webarchive
• NBODY Code
• pC++ Treecode
• HTML5/JavaScript Example Graphical Barnes-Hut Simulation
• PEPC — The Pretty Efficient Parallel Coulomb solver