Барнс-Гат: Моделювання Галактики Без Обчислення Кожного Пара Пару

Задача про N тіла – це стіна пар

Моделювання гравітації для n тіл чесним способом означає обчислення сили між кожною парою: n(n-1)/2 оцінок сили на крок часу. Поділіть кількість тіл у два рази, і робота збільшиться вчетверо. Цей підхід з прямою сумою є точним – і для кількох тисяч тіл на сучасному GPU він навіть практичний — але для десятків або сотень тисяч частинок у моделі галактики чи великого гравітаційного кластера, O(n²) стає вузьким місцем. Джош Барнс та Піт Хат опублікували алгоритм, який обходить цю проблему в 1986 році.

Інсайт: віддалений кластер виглядає як точка

Ньютон століття тому показав, що сферично симетричне розподілення маси притягує зовнішні тіла точно так само, ніби вся його маса сконцентрована в центрі. Barnes-Hut спирається на приблизну версію цієї ж ідеї: з достатньої відстані цілий кластер тіл гравітаційно нерозрізняється від однієї точкової маси, що знаходиться в центрі мас кластера. Замість того, щоб сумувати притягання кожного окремого тіла у віддаленому кластері, їх підсумовують один раз заздалегідь і обробляють кластер як одне тіло для будь-чого далеко розташованого.

Щоб визначити, що вважається «кластером», а що – «достатньо близько», Barnes-Hut будує квадродерево (октадерево у 3D) по всіх тілах на початку кожного часового кроку. Кожен вузол зберігає загальну масу та центр мас усіх тіл, що знаходяться під ним – розраховується знизу вгору одним проходом після побудови дерева.

Тест тети

Обчислення сили на тіло передбачає обхід дерева від кореня і, на кожному вузлі, застосування одного тесту: порівняння фізичного розміру вузла s з його відстанню d до тіла, яке оцінюється.

force(тіло, вузол): s = вузол.ширина // розмір області, яку охоплює цей вузол d = відстань(тіло, центр_маси вузла) якщо s / d < тета АБО вузол є листовим з одним іншим тілом: повертати гравітацію(тіло, сумарна_маса вузла, центр_маси вузла) // вважати як 1 точку інакше: повернути суму(force(тіло, дитина) для дитини в вузлі.діти) Якщо s/d невелике – вузол малий порівняно з тим, наскільки він віддалений – весь піддерево стискається в єдину точку-масу взаємодії та рекурсія там зупиняється, незалежно від кількості тіл, що містяться в цьому вузлі. Якщо s/d велике – вузол або занадто близько, або занадто великий, щоб довіряти йому як одній точці, і алгоритм сходить у його чотири дитини для отримання більш точної відповіді. Порогове значення тета (θ) - це єдильний регулятор, який контролює весь баланс: θ = 0 змушує алгоритм йти донизу до окремих тіл для кожної взаємодії, відновлюючи точний O(n²) підсумок; θ близько 0.5 – 1.0 є типовим робочим діапазоном, обмінюючи невелику, контрольовану кількість точності на величезний приріст швидкості.

force(body, node):
    s = node.width               // size of the region this node covers
    d = distance(body, node.centerOfMass)
    if s / d < theta OR node is a leaf with one other body:
        return gravity(body, node.totalMass, node.centerOfMass)   // treat as 1 point
    else:
        return sum(force(body, child) for child in node.children) // look closer

Чому це має складність O(n log n)

Побудова дерева з n тіл коштує O(n log n), як і будь-яка побудова збалансованого просторового дерева. Обчислення сили, що діє на одне тіло, яке торкається, в середньому, займає O(log n) вузлів дерева: більша частина простору знаходиться далеко і підсумовується в одному вузку, а лише кілька тіл, які дійсно розташовані поруч, змушують рекурсію заглиблюватися. Множення O(log n) на тіло на n тіл дає загальну вартість обчислення сили для одного кроку часу O(n log n) – така сама асимптотична класифікація, як і у сортуванні порівнянням, і значно краща за O(n²) прямого підсумовування, коли n досягає тисяч.

Що коштує Barnes-Hut

Прискорення не є безкоштовним. Приближення центра маси вносить реальну похибку сили, коли θ більше нуля, і ця похибка найбільша у випадках близьких зіткнень між кластерами схожих розмірів – саме ті ситуації, наприклад, майже зіткнення двох зоряних кластерів, де найчастіше потрібна точність. Професійні астрофізичні коди вирішують це за допомогою розширення мультиполя (додавання чотиричного моменту та вище, а не лише загальної маси та центру маси), щоб зменшити похибку при заданому θ, і з використанням адаптивного θ, який автоматично зменшується в щільних областях. Дерево також необхідно повністю переробити (або обережно оновити) на кожному кроці, коли тіла рухаються, що само по собі є домінуючою вартістю у багатьох реалізаціях – хороша причина, чому конструкція просторового дерева отримує таку увагу в кодах N-тіла.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Barnes-Hut N-body і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.