Моделирование Barnes – Hut

Моделирование 100 тел с деревом Барнса-Хат, визуально в виде синих прямоугольников.

Моделирование Barnes-Hut (названное в честь Josh Barnes и Пита Hut ) является приближенным алгоритмом для выполнения п -Боди моделирования . Он примечателен тем, что имеет порядок O ( n log n ) по сравнению с алгоритмом прямой суммы, который был бы O ( n ² ). ^[1]

Объем моделирования обычно делится на кубические ячейки через октодерево (в трехмерном пространстве), так что только частицы из соседних ячеек нужно обрабатывать индивидуально, а частицы в удаленных ячейках можно рассматривать как одну большую частицу с центром в центр масс клетки (или как мультипольное разложение низкого порядка ). Это может значительно уменьшить количество взаимодействий пар частиц, которые необходимо вычислить.

Некоторые из наиболее требовательных проектов высокопроизводительных вычислений занимаются вычислительной астрофизикой с использованием алгоритма древовидного кода Барнса – Хата, такого как DEGIMA . ^[2]^{[ необходима ссылка ]}

Алгоритм [ править ]

Дерево Барнса-Хат [ править ]

В трехмерном п -Боди моделирования , алгоритм Барнс-Хата рекурсивно делит п тела в группы, сохраняя их в октодереве (или квадратор дереве в 2D моделировании). Каждый узел в этом дереве представляет собой область трехмерного пространства. Самый верхний узел представляет все пространство, а его восемь дочерних узлов представляют восемь октантов.пространства. Пространство рекурсивно делится на октанты до тех пор, пока каждое подразделение не будет содержать 0 или 1 тела (некоторые области не имеют тел во всех своих октантах). В октодереве есть два типа узлов: внутренние и внешние. Внешний узел не имеет дочерних элементов и либо пуст, либо представляет собой одно тело. Каждый внутренний узел представляет группу тел под ним и хранит центр масс и общую массу всех своих дочерних тел.

Распределение частиц, напоминающее две соседние галактики.
Завершите дерево Барнс-Хат. (Узлы, не содержащие частиц, не отрисовываются)
Узлы дерева Барнса – Хата, используемые для расчета силы, действующей на частицу в исходной точке.
Воспроизвести медиа
n - Моделирование тела на основе алгоритма Барнса – Хата.

Расчет силы, действующей на тело [ править ]

Чтобы вычислить чистую силу, действующую на конкретное тело, узлы дерева пересекаются, начиная с корня. Если центр масс внутреннего узла находится достаточно далеко от тела, тела, содержащиеся в этой части дерева, рассматриваются как одна частица, положение и масса которой являются соответственно центром масс и общей массой внутреннего узла. Если внутренний узел находится достаточно близко к телу, процесс повторяется для каждого из его дочерних узлов.

Находится ли узел достаточно далеко от тела или недостаточно, зависит от частного , где s - ширина области, представленной внутренним узлом, а d - расстояние между телом и центром масс узла. Узел находится достаточно далеко, когда это отношение меньше порогового значения θ . Параметр θ определяет точность моделирования; большие значения θ увеличивают скорость моделирования, но снижают его точность. Если θ = 0, никакой внутренний узел не рассматривается как единое тело, и алгоритм вырождается в алгоритм прямой суммы. ${\ displaystyle s / d}$

См. Также [ править ]

Ссылки и источники [ править ]

использованная литература

^ Пфальцнер, Сюзанна; Гиббон, Пол (1996). Многотельные древовидные методы в физике . Кембридж [ua]: Cambridge Univ. Нажмите . стр. 2 , 3. ISBN 978-0-521-49564-6.
^ Т. Хамада; и другие. (2009). «Новый параллельный алгоритм с несколькими обходами для древовидного кода Barnes-Hut на графических процессорах - на пути к экономичному высокопроизводительному моделированию N-тела». Комп. Sci. Res. Dev . 24 (1-2): 21-31. DOI : 10.1007 / s00450-009-0089-1 . S2CID 31071570 .

Источники

Дж. Барнс и П. Хат (декабрь 1986 г.). «Иерархический алгоритм вычисления силы O ( N log N )». Природа . 324 (4): 446–449. Bibcode : 1986Natur.324..446B . DOI : 10.1038 / 324446a0 . S2CID 4267861 .
Я. Дубинский (октябрь 1996 г.). «Код параллельного дерева». Новая астрономия . 1 (2): 133–147. arXiv : astro-ph / 9603097v1 . Bibcode : 1996NewA .... 1..133D . DOI : 10.1016 / S1384-1076 (96) 00009-7 . S2CID 119464486 .
У. Беччиани; Р. Ансалониб; В. Антонуччо-Делогуа; Г. Эрбакчич; М. Гамбераа и А. Паглиарод (октябрь 1997 г.). «Код параллельного дерева для моделирования большого N- тела: динамическое распределение нагрузки и распределение данных в системе CRAY T3D». Компьютерная физика . 106 (1–2): 105–113. arXiv : физика / 9709003 . Bibcode : 1997CoPhC.106..105B . DOI : 10.1016 / S0010-4655 (97) 00102-1 . S2CID 18428101 .
Т. Вентимилья и К. Уэйн. «Алгоритм Барнса – Хата» . Проверено 30 марта 2012 года .

Внешние ссылки [ править ]

Древовидные коды, Дж. Барнс
Параллельный TreeCode
HTML5 / JavaScript Пример графического моделирования Barnes – Hut
PEPC - довольно эффективный параллельный кулоновский решатель , параллельный код дерева Барнса – Хата с открытым исходным кодом и заменяемым ядром взаимодействия для множества приложений.
Программа параллельного графического моделирования N-body с быстрым обходом дерева частиц без стека
Симулятор галактики Barnes-Hut на сайте beltoforion.de

[1] Пфальцнер, Сюзанна; Гиббон, Пол (1996). Многотельные древовидные методы в физике . Кембридж [ua]: Cambridge Univ. Нажмите . стр. 2 , 3. ISBN 978-0-521-49564-6.

[2] Т. Хамада; и другие. (2009). «Новый параллельный алгоритм с несколькими обходами для древовидного кода Barnes-Hut на графических процессорах - на пути к экономичному высокопроизводительному моделированию N-тела». Комп. Sci. Res. Dev . 24 (1-2): 21-31. DOI : 10.1007 / s00450-009-0089-1 . S2CID 31071570 .

[1]