Метод Барнса-Хата — различия между версиями

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
(Первый этап)
(Второй этап)
Строка 14: Строка 14:
 
А) если узел терминальный, то к результату просто добавляется сила, действующая со стороны этого узла;
 
А) если узел терминальный, то к результату просто добавляется сила, действующая со стороны этого узла;
 
<br>
 
<br>
Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация; происходит проверка того будет ли эта аппроксимация достаточно точной:
+
Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация. С помощью критерия допустимости происходит проверка точности аппроксимации:
* если да, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;
+
* если критерий удовлетворен, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;
 
* если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов.
 
* если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов.
  

Версия 11:47, 13 сентября 2016

Barns1.png

Аннотация

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

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

Первый этап

Barns2.png

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

Второй этап

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

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

Третий этап

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


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

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


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

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



См. также


Ссылки