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

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

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

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

Некоторые из самых требовательных высокопроизводительные вычисления проекты делают вычислительная астрофизика используя алгоритм древовидного кода Барнса – Хата, например ДЕГИМА.^[2]^{[нужна цитата ]}

Алгоритм

Дерево Барнса-Хат

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

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

п-Моделирование тела на основе алгоритма Барнса – Хата.

Расчет силы, действующей на тело

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

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

Смотрите также

Ссылки и источники

Рекомендации

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

Источники

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

внешняя ссылка

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

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

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

[1]

[2]