Редактирование: Метод Барнса-Хата

[[Виртуальная лаборатория]] > [[Метод Барнса-Хата]] <HR>

 

[[File: Barns1.png|thumb|400px|right|Результат моделирования формирования планетной системы

Земля-Луна в результате гравитационного коллапса пылевого облака]]

Для оптимизации некоторых задач, решаемых методом динамики частиц (таких, как моделирование образования Солнечной системы), используются иерархические методы. Они наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до <math>10^9</math>, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма — быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил.

 

В данной статье рассматривается процесс реализации алгоритма Барнса-Хата на примере двумерного случая.

[[Image: Barns2.png|thumb|210px|right|Пример разбиения иерархического пространства на ячейки для двумерного случая]]  

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

А) если узел терминальный (не имеющий дочерних элементов), то к результату просто добавляется сила, действующая со стороны этого узла;

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

* если критерий удовлетворен, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;

* если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов.

Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины <math>\Theta</math> — так называемого угла раскрытия. В физическом смысле <math>\Theta</math> это максимальный угол, под которым должна быть видна ячейка из местоположения частицы, для которой вычисляется сила, чтобы была использована мультипольная аппроксимация. Наиболее распространенными являются следующие три типа МАС:

1) Barnes-Hut (BH) MAC: <math> s/r < \Theta </math>, где <math>r</math> - расстояние от частицы до центра масс ячейки, <math>s</math> - размер ячейки.

2) Min-distance (MD) MAC: <math> s/r < \Theta </math>, где <math>r</math> - расстояние от частицы до границы ячейки, <math>s</math> - размер ячейки.

3) Bmax MAC: <math> b_{max}/r < \Theta </math>, где <math>b_{max}</math> - максимальное расстояние от центра масс ячейки до ее границы, <math>r</math> - расстояние от частицы до центра масс ячейки.

= Программа =

* Левой клавишей мыши частицы можно добавлять и перемещать.

* Правой клавишей мыши частицы можно удалять.

 

 

 

 

 

[[Category: Виртуальная лаборатория]]