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

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
(→‎Второй этап)
(→‎Первый этап)
 
(не показано 59 промежуточных версий 3 участников)
Строка 1: Строка 1:
−
[[Image: Barns1.png|400px|right]]  
+
[[Виртуальная лаборатория]] > [[Метод Барнса-Хата]] <HR>
 +
 
 +
[[File: Barns1.png|thumb|400px|right|Результат моделирования формирования планетной системы
 +
Земля-Луна в результате гравитационного коллапса пылевого облака]]
  
 
= Аннотация =
 
= Аннотация =
−
Иерархические методы наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до 10^9, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил.
+
Для оптимизации некоторых задач, решаемых методом динамики частиц (таких, как моделирование образования Солнечной системы), используются иерархические методы. Они наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до <math>10^9</math>, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма — быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил.
  
 +
В данной статье рассматривается процесс реализации алгоритма Барнса-Хата на примере двумерного случая.
  
 
= Описание метода =
 
= Описание метода =
 
== Первый этап ==
 
== Первый этап ==
−
[[Image: Barns2.png|200px|right]]  
+
[[Image: Barns2.png|thumb|210px|right|Пример разбиения иерархического пространства на ячейки для двумерного случая]]  
−
Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозиции пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан рисунке справа. Ячейки в нем соответвуют узлам дерева, частицы в них листьям.
+
Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозицией пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответствуют узлам дерева, частицы в них — листьям.
  
 
== Второй этап ==
 
== Второй этап ==
 
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме:
 
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме:
−
А) если узел терминальный, то к результату просто добавляется сила, действующая со стороны этого узла;
+
<br>
−
Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация; происходит проверка того будет ли эта аппроксимация достаточно точной:
+
А) если узел терминальный (не имеющий дочерних элементов), то к результату просто добавляется сила, действующая со стороны этого узла;
−
** если да, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;
+
<br>
−
** если нет, то пункт 2 рекурсивно повторяется для всех дочерних узлов.
+
Б) если узел не терминальный, то для потенциала, создаваемого частицами данного узла, может быть вычислена аппроксимация. С помощью критерия допустимости происходит проверка точности аппроксимации:
 +
* если критерий удовлетворен, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;
 +
* если нет, то этап 2 рекурсивно повторяется для всех дочерних узлов.
  
 
== Третий этап ==
 
== Третий этап ==
 
Производится интегрирование уравнений движения и пересчет скоростей и координат частиц.
 
Производится интегрирование уравнений движения и пересчет скоростей и координат частиц.
−
 
  
 
== Дополнение к этапу 2-Б ==
 
== Дополнение к этапу 2-Б ==
−
Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины "тета" так называемого угла раскрытия. В физическом смысле "тета" это максимальный угол, под которым должна быть видна ячейка из местоположения частицы, для которой вычисляется сила, чтобы была использована мультипольная аппроксимация. Наиболее распространенными являются следующие три типа МАС:
+
Критерий принятия решения в пункте 2-Б в литературе обычно называется критерием допустимости (Multipole Acceptance Criteria (MAC)). Почти всегда он сводится к тому, что для частиц, находящихся близко, происходит прямое вычисление сил, а для удаленных частиц используется аппроксимация. Обычно МАС описывается при помощи величины <math>\Theta</math> — так называемого угла раскрытия. В физическом смысле <math>\Theta</math> это максимальный угол, под которым должна быть видна ячейка из местоположения частицы, для которой вычисляется сила, чтобы была использована мультипольная аппроксимация. Наиболее распространенными являются следующие три типа МАС:
−
1) Barnes-Hut (BH) MAC s/r < "teta", где r - расстояние от частицы до центра масс ячейки, s - размер ячейки.
+
<br>
−
2) Min-distance (MD) MAC s/r < "teta", где r - расстояние от частицы до границы ячейки, s - размер ячейки.
+
1) Barnes-Hut (BH) MAC: <math> s/r < \Theta </math>, где <math>r</math> - расстояние от частицы до центра масс ячейки, <math>s</math> - размер ячейки.
−
3) Bmax MAC b_max/r < "teta", где b_max - максимальное рассиояние от центра масс ячейки до ее границы, r - расстояние от частицы до центра масс ячейки.
+
<br>
 +
2) Min-distance (MD) MAC: <math> s/r < \Theta </math>, где <math>r</math> - расстояние от частицы до границы ячейки, <math>s</math> - размер ячейки.
 +
<br>
 +
3) Bmax MAC: <math> b_{max}/r < \Theta </math>, где <math>b_{max}</math> - максимальное расстояние от центра масс ячейки до ее границы, <math>r</math> - расстояние от частицы до центра масс ячейки.
 +
<br>
 
Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой.
 
Если условие МАС выполняется, то мультипольная аппроксимация в данном случае считается допустимой.
  
−
== Программа ==
+
= Программа =
 
В данной программе используется критерий допустимости Mid-distance.
 
В данной программе используется критерий допустимости Mid-distance.
−
{{#widget:Iframe |url=http://tm.spbstu.ru/htmlets/Alexandrov_S_D/Barns_hat/Balls_v4_release.html |width=800|height=800 |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 |Материал диссертации]] (Автор [[Ле-Захаров Александр|Александр Ле-Захаров]])
 +
* [[Проект "Земля - Луна"]]
 +
* [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: Виртуальная лаборатория]]

Текущая версия на 12:48, 19 сентября 2016

Виртуальная лаборатория > Метод Барнса-Хата
Результат моделирования формирования планетной системы Земля-Луна в результате гравитационного коллапса пылевого облака

Аннотация[править]

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

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

Описание метода[править]

Первый этап[править]

Пример разбиения иерархического пространства на ячейки для двумерного случая

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

Второй этап[править]

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

  • если критерий удовлетворен, то аппроксимация вычисляется, и на этом обход данной ветки дерева завершается;
  • если нет, то этап 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.


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

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


Разработчик программы: Цветков Денис, при разработке программы были использованы материалы диссертации Александра Ле-Захарова.

Материал данной страницы скомпонован Сергеем Александровым.

См. также[править]

Источник — «http://tm.spbstu.ru/?title=Метод_Барнса-Хата&oldid=44223»