Редактирование: Метод Барнса-Хата
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
− | [[ | + | [[Image: Barns1.png|400px|right]] |
− | |||
− | |||
− | |||
= Аннотация = | = Аннотация = | ||
− | + | Иерархические методы наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до <math>10^9</math>, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил. | |
− | |||
− | |||
= Описание метода = | = Описание метода = | ||
== Первый этап == | == Первый этап == | ||
− | [[Image: Barns2.png| | + | [[Image: Barns2.png|200px|right]] |
− | Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической | + | Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозиции пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответвуют узлам дерева, частицы в них листьям. |
== Второй этап == | == Второй этап == | ||
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме: | Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме: | ||
<br> | <br> | ||
− | А) если узел терминальный | + | А) если узел терминальный, то к результату просто добавляется сила, действующая со стороны этого узла; |
<br> | <br> | ||
− | Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация | + | Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация; происходит проверка того будет ли эта аппроксимация достаточно точной: |
− | * если | + | * если да, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается; |
* если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов. | * если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов. | ||
== Третий этап == | == Третий этап == | ||
Производится интегрирование уравнений движения и пересчет скоростей и координат частиц. | Производится интегрирование уравнений движения и пересчет скоростей и координат частиц. | ||
+ | |||
== Дополнение к этапу 2-Б == | == Дополнение к этапу 2-Б == | ||
− | Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины <math>\Theta</math> | + | Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины <math>\Theta</math> так называемого угла раскрытия. В физическом смысле <math>\Theta</math> это максимальный угол, под которым должна быть видна ячейка из местоположения частицы, для которой вычисляется сила, чтобы была использована мультипольная аппроксимация. Наиболее распространенными являются следующие три типа МАС: |
<br> | <br> | ||
1) Barnes-Hut (BH) MAC: <math> s/r < \Theta </math>, где <math>r</math> - расстояние от частицы до центра масс ячейки, <math>s</math> - размер ячейки. | 1) Barnes-Hut (BH) MAC: <math> s/r < \Theta </math>, где <math>r</math> - расстояние от частицы до центра масс ячейки, <math>s</math> - размер ячейки. | ||
Строка 33: | Строка 29: | ||
2) Min-distance (MD) 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> - размер ячейки. | ||
<br> | <br> | ||
− | 3) Bmax MAC: <math> b_{max}/r < \Theta </math>, где <math>b_{max}</math> - максимальное | + | 3) Bmax MAC: <math> b_{max}/r < \Theta </math>, где <math>b_{max}</math> - максимальное рассиояние от центра масс ячейки до ее границы, <math>r</math> - расстояние от частицы до центра масс ячейки. |
<br> | <br> | ||
Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой. | Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой. | ||
− | = Программа = | + | == Программа == |
В данной программе используется критерий допустимости Mid-distance. | В данной программе используется критерий допустимости Mid-distance. | ||
''Комментарий к программе'': | ''Комментарий к программе'': | ||
− | * Левой клавишей мыши частицы | + | * Левой клавишей мыши добавляются частицы |
− | * Правой клавишей мыши частицы | + | * Правой клавишей мыши удаляются частицы |
{{#widget:Iframe |url=http://tm.spbstu.ru/htmlets/Alexandrov_S_D/Barns_Hat/Balls_v4_release.html |width=650|height=650 |border=0 }} | {{#widget:Iframe |url=http://tm.spbstu.ru/htmlets/Alexandrov_S_D/Barns_Hat/Balls_v4_release.html |width=650|height=650 |border=0 }} | ||
− | |||
− | |||
− | |||
= См. также = | = См. также = | ||
− | * [[Медиа: Lezakharov_disser_2010.pdf |Материал диссертации]] (Автор [[Ле-Захаров Александр| | + | * Разработчик программы [[Цветков Денис]] |
− | + | * [[Медиа: Lezakharov_disser_2010.pdf |Материал диссертации]] (Автор [[Ле-Захаров Александр|Ле-Захаров Александр]]) | |
− | |||
+ | ='''Ссылки'''= | ||
+ | * [[Виртуальная лаборатория]] | ||
+ | <br> | ||
[[Category: Виртуальная лаборатория]] | [[Category: Виртуальная лаборатория]] | ||
+ | [[Category: Программирование]] | ||
+ | [[Category: JavaScript]] |