Метод Барнса-Хата — различия между версиями
Денис (обсуждение | вклад) (→Первый этап) |
Денис (обсуждение | вклад) (→Первый этап) |
||
| (не показаны 24 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
| − | [[ | + | [[Виртуальная лаборатория]] > [[Метод Барнса-Хата]] <HR> |
| + | |||
| + | [[File: Barns1.png|thumb|400px|right|Результат моделирования формирования планетной системы | ||
| + | Земля-Луна в результате гравитационного коллапса пылевого облака]] | ||
= Аннотация = | = Аннотация = | ||
| − | + | Для оптимизации некоторых задач, решаемых методом динамики частиц (таких, как моделирование образования Солнечной системы), используются иерархические методы. Они наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до <math>10^9</math>, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма — быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил. | |
| + | |||
| + | В данной статье рассматривается процесс реализации алгоритма Барнса-Хата на примере двумерного случая. | ||
= Описание метода = | = Описание метода = | ||
== Первый этап == | == Первый этап == | ||
| − | [[Image: Barns2.png| | + | [[Image: Barns2.png|thumb|210px|right|Пример разбиения иерархического пространства на ячейки для двумерного случая]] |
Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозицией пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответствуют узлам дерева, частицы в них — листьям. | Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозицией пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответствуют узлам дерева, частицы в них — листьям. | ||
| Строка 12: | Строка 17: | ||
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме: | Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме: | ||
<br> | <br> | ||
| − | А) если узел терминальный, то к результату просто добавляется сила, действующая со стороны этого узла; | + | А) если узел терминальный (не имеющий дочерних элементов), то к результату просто добавляется сила, действующая со стороны этого узла; |
<br> | <br> | ||
| − | Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация | + | Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация. С помощью критерия допустимости происходит проверка точности аппроксимации: |
| − | * если | + | * если критерий удовлетворен, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается; |
* если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов. | * если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов. | ||
== Третий этап == | == Третий этап == | ||
Производится интегрирование уравнений движения и пересчет скоростей и координат частиц. | Производится интегрирование уравнений движения и пересчет скоростей и координат частиц. | ||
| − | |||
== Дополнение к этапу 2-Б == | == Дополнение к этапу 2-Б == | ||
| − | Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины <math>\Theta</math> так называемого угла раскрытия. В физическом смысле <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> - размер ячейки. | ||
| Строка 29: | Строка 33: | ||
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> | ||
Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой. | Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой. | ||
| Строка 38: | Строка 42: | ||
''Комментарий к программе'': | ''Комментарий к программе'': | ||
| − | * Левой клавишей мыши | + | * Левой клавишей мыши частицы можно добавлять и перемещать. |
| − | * Правой клавишей мыши | + | * Правой клавишей мыши частицы можно удалять. |
{{#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 |Материал диссертации]] (Автор [[Ле-Захаров Александр|Ле-Захаров | + | * [[Проект "Земля - Луна"]] |
| + | * [https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85) Дерево_(структура_данных)] | ||
| − | |||
| − | |||
| − | |||
| − | |||
[[Category: Виртуальная лаборатория]] | [[Category: Виртуальная лаборатория]] | ||
| − | |||
| − | |||
Текущая версия на 12:48, 19 сентября 2016
Виртуальная лаборатория > Метод Барнса-Хата
Содержание
Аннотация[править]
Для оптимизации некоторых задач, решаемых методом динамики частиц (таких, как моделирование образования Солнечной системы), используются иерархические методы. Они наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до , в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма — быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил.
В данной статье рассматривается процесс реализации алгоритма Барнса-Хата на примере двумерного случая.
Описание метода[править]
Первый этап[править]
Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозицией пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответствуют узлам дерева, частицы в них — листьям.
Второй этап[править]
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме:
А) если узел терминальный (не имеющий дочерних элементов), то к результату просто добавляется сила, действующая со стороны этого узла;
Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация. С помощью критерия допустимости происходит проверка точности аппроксимации:
- если критерий удовлетворен, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;
- если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов.
Третий этап[править]
Производится интегрирование уравнений движения и пересчет скоростей и координат частиц.
Дополнение к этапу 2-Б[править]
Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины — так называемого угла раскрытия. В физическом смысле это максимальный угол, под которым должна быть видна ячейка из местоположения частицы, для которой вычисляется сила, чтобы была использована мультипольная аппроксимация. Наиболее распространенными являются следующие три типа МАС:
1) Barnes-Hut (BH) MAC: , где - расстояние от частицы до центра масс ячейки, - размер ячейки.
2) Min-distance (MD) MAC: , где - расстояние от частицы до границы ячейки, - размер ячейки.
3) Bmax MAC: , где - максимальное расстояние от центра масс ячейки до ее границы, - расстояние от частицы до центра масс ячейки.
Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой.
Программа[править]
В данной программе используется критерий допустимости Mid-distance.
Комментарий к программе:
- Левой клавишей мыши частицы можно добавлять и перемещать.
- Правой клавишей мыши частицы можно удалять.
Разработчик программы: Цветков Денис, при разработке программы были использованы материалы диссертации Александра Ле-Захарова.
Материал данной страницы скомпонован Сергеем Александровым.
