Метод Барнса-Хата

Аннотация

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

Описание метода

Первый этап

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

Второй этап

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

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

Третий этап

Производится интегрирование уравнений движения и пересчет скоростей и координат частиц.

Дополнение к этапу 2-Б

Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины "тета" так называемого угла раскрытия. В физическом смысле "тета" это максимальный угол, под которым должна быть видна ячейка из местоположения частицы, для которой вычисляется сила, чтобы была использована мультипольная аппроксимация. Наиболее распространенными являются следующие три типа МАС:
1) Barnes-Hut (BH) MAC: [math] s/r \lt \Theta [/math], где [math]r[/math] - расстояние от частицы до центра масс ячейки, [math]s[/math] - размер ячейки.
2) Min-distance (MD) MAC: [math] s/r \lt \Theta [/math], где [math]r[/math] - расстояние от частицы до границы ячейки, [math]s[/math] - размер ячейки.
3) Bmax MAC: [math] b_{max}/r \lt \Theta [/math], где [math]b_{max}[/math] - максимальное рассиояние от центра масс ячейки до ее границы, [math]r[/math] - расстояние от частицы до центра масс ячейки.
Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой.

Программа

В данной программе используется критерий допустимости Mid-distance.

Комментарий к программе:

• Левой клавишей мыши добавляются частицы
• Правой клавишей мыши удаляются частицы