Гравітаційна задача N тіл — обчислення сили, що діє на кожну частинку з боку всіх інших — наївно потребує O(n²) обчислень на крок, що стає непрактичним для великих n. Алгоритм Барнса–Гата (1986) знижує складність до O(n log n), рекурсивно розбиваючи простір на квадродерево (у 2D) і замінюючи далекі кластери тіл одним центром мас, коли відношення розміру комірки до відстані s/d менше порогового кута θ. Він лежить в основі сучасних кодів моделювання галактик (наприклад, GADGET) і використовується у всіх космологічних симуляціях формування великомасштабної структури Всесвіту.
Симуляція дозволяє змінювати кількість тіл N (до 2 000), кут розкриття θ (0 = точно, 1,5 = дуже наближено), гравітаційне пом'якшення ε і крок за часом dt у чотирьох початкових пресетах: газова хмара, дві галактики, що зливаються, центральна маса + хмара і кільце. Увімкнення накладення квадродерева показує, які комірки апроксимуються (блакитний), а які — рекурсуються (рожевий).
Що таке задача N тіл?
Гравітаційна задача N тіл: за відомими початковими положеннями та швидкостями N точкових мас визначити їхні майбутні положення під дією ньютонівської гравітації F = Gm₁m₂/r². Для N = 2 рішення — конічний переріз (орбіта Кеплера); для N ≥ 3 загального аналітичного розв'язку не існує й необхідна чисельна інтеграція. Кожен крок наїву коштує O(n²) обчислень сили, що робить великі симуляції (мільйони зірок) нездійсненними без алгоритму апроксимації.
Як працює квадродерево Барнса–Гата?
На кожному кроці алгоритм вставляє всі тіла в квадродерево — рекурсивний поділ 2D-простору на чотири рівних квадрати. Щоб обчислити силу на тіло i, дерево обходять від кореня: якщо комірка достатньо далеко (s/d < θ), вся вона апроксимується своєю загальною масою та центром мас. Інакше вузол розкривається й перевіряються дочірні. Це зменшує типову кількість взаємодій з O(n) до O(log n) на тіло.
Що контролює кут розкриття θ?
θ — ключовий параметр компромісу між точністю і швидкістю. При θ = 0 кожна комірка завжди розкривається, відтворюючи точну суму O(n²). При θ = 0,5 (типове виробниче значення) алгоритм приблизно на 95% точний порівняно з прямим підсумовуванням при прискоренні в 30–100 разів для n = 1 000. При θ = 1,5 швидкість максимальна, але структура далеких галактик помітно розмивається.
Гравітаційне пом'якшення замінює закон 1/r² на 1/(r² + ε²), що запобігає розходженню сили до нескінченності при близьких зближеннях. Без пом'якшення близькі зустрічі потребували б нескінченно малого кроку за часом, а симуляція «вибухала» б нереалістичними швидкостями розсіювання. Довжина пом'якшення ε зазвичай становить частку середньої відстані між частинками; у реальних космологічних симуляціях це ~1 кпк для частинок темної матерії.
Квадродерево має O(n) вузлів і глибину O(log n). Для кожного з n тіл обхід дерева відвідує O(log n) вузлів до того, як достатньо комірок задовольнять критерій θ. Множення дає O(n log n) обчислень сили на крок. Побудова дерева також коштує O(n log n). Для n = 10 000 прискорення порівняно з O(n²) становить 100–1 000 разів.
Коли дві галактики проходять крізь одна одну, припливні сили зривають зірки з периферії й жбурляють їх у довгі «припливні хвости», що простягаються на мільйони світлових років. Зоряні диски проходять крізь одна одну майже безперешкодно, оскільки зірки розділені величезними відстанями. Чумацький Шлях і галактика Андромеди наближаються одна до одної й мають злитися приблизно через 4,5 млрд років.
Симуляція відображає кількість обчислень Барнса–Гата поруч із наївним n(n–1)/2. Для n = 500 і θ = 0,7 БГ зазвичай обчислює ~3 000–5 000 пар на крок замість 499, даючи прискорення 50–100 разів. При n = 2 000 наївний метод потребує майже 2 млн пар на крок, тоді як БГ — лише ~20 000.
Кінетична енергія KE = Σ ½mᵢvᵢ², потенціальна PE = –Σᵢ≠ⱼ Gmᵢmⱼ/rᵢⱼ. У справжній консервативній симуляції повна енергія E = KE + PE має бути сталою, але чисельна інтеграція вносить похибки. Симплектичний інтегратор «жаб'ячий стрибок», що використовується тут, зберігає модифікований гамільтоніан і тримає дрейф енергії дуже малим у довгостроковій перспективі.
Коли ввімкнено «Виділити θ-спуск для вибраного тіла», клацання на тілі показує, які комірки квадродерева воно апроксимує (блакитний) і які — рекурсує (рожевий). Одна й та сама комірка може оброблятися по-різному для тіл у різних положеннях, ілюструючи адаптивний характер Барнса–Гата.
Так — сімейство кодів GADGET (Шпрінгель, 2001, 2005) використовує ієрархічне дерево, дуже схоже на Барнса–Гата, і застосовувалося для Millennium Simulation (10 млрд частинок) та IllustrisTNG. Сучасні коди часто поєднують БГ із методами швидких мультиполів (FMM), частинок-сіток (PM) або паралелізмом на GPU для симуляцій до 10¹² частинок.
Кожен внутрішній вузол квадродерева зберігає загальну масу M = Σmᵢ і середньозважену за масою позицію r_cm = Σmᵢrᵢ / M усіх тіл у комірці. Коли далека комірка апроксимується, гравітаційна сила обчислюється так, ніби вся маса зосереджена в r_cm. Ця монопольна апроксимація точна до першого порядку по s/d; мультипольні розкладання вищих порядків дають кращу точність ціною більших витрат.