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

A 100-body simulation with the Barnes-Hut tree visually represented as blue boxes.

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

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

Моделювання простору виконується, як правило, поділом простору на комірки, так, що тіла в сусідніх комірках розглядаються індивідуально, а тіла в далеких комірках розглядаються як одна велика частка з центром в точці її центру мас, за рахунок чого досягається значне скорочення обчислень.

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

Застосування

• Gravit

Див. також

• Задача двох тіл

Посилання

• Treecodes, J. Barnes
• Parallel TreeCode
• NBODY Code
• pC++ Treecode
• HTML5/JavaScript Example Graphical Barnes-Hut Simulation
• PEPC - The Pretty Efficient Parallel Coulomb solver

Джерела

• J. Barnes and P. Hut A hierarchical O(N log N) force-calculation algorithm // Nature. — Т. 324. — (December 1986) (4) С. 446–449. DOI:10.1038/324446a0.
• J. Dubinski A Parallel Tree Code // New Astronomy. — Т. 1. — (October 1996) (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 A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system // Computer Physics Communications. — Т. 106. — (October 1997) (1–2) С. 105–113. DOI:10.1016/S0010-4655(97)00102-1.
• T. Ventimiglia, and K. Wayne. «The Barnes-Hut Algorithm». Процитовано 30 March 2012.