Моделирование Барнса – Хата

Моделирование Барнса-Хата (названное в честь Джоша Барнса и Пита Хата ) — это аппроксимационный алгоритм для выполнения n моделирования -тел . Он примечателен тем, что имеет порядок O( n log n ) по сравнению с алгоритмом прямой суммы, который будет равен O( n ²). ^{[ 1 ]}

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

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

Алгоритм

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

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

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

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

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

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

См. также

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

Ссылки

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

Источники

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

Внешние ссылки

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

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

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

[ 1 ]

[ 2 ]

v т и Численное интегрирование
Формулы Ньютона–Котеса	Правило трапеции Правило Симпсона Правило Симпсона 3/8 Адаптивный метод Симпсона правило Буля метод Ромберга
Гауссова квадратура	Квадратура Гаусса – Эрмита Квадратура Гаусса – Якоби Квадратурная формула Гаусса – Кронрода Квадратура Гаусса – Лагерра Квадратура Гаусса – Лежандра Квадратура Чебышева – Гаусса
Другой	Моделирование Барнса – Хата Байесовская квадратура Квадратура Кленшоу – Кертиса Квадратурная вена Квадратура Лебедева Тан-квадратура рождения