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

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
(Первый этап)
 
(не показано 40 промежуточных версий 3 участников)
Строка 1: Строка 1:
[[Image: Barns1.png|400px|right]]  
+
[[Виртуальная лаборатория]] > [[Метод Барнса-Хата]] <HR>
 +
 
 +
[[File: Barns1.png|thumb|400px|right|Результат моделирования формирования планетной системы
 +
Земля-Луна в результате гравитационного коллапса пылевого облака]]
  
 
= Аннотация =
 
= Аннотация =
Иерархические методы наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до <math>10^9</math>, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил.
+
Для оптимизации некоторых задач, решаемых методом динамики частиц (таких, как моделирование образования Солнечной системы), используются иерархические методы. Они наиболее неприхотливы к различным особенностям физической модели, в частности к скачкам в распределении частиц. На доступных на сегодняшний день аппаратных ресурсах они позволяют проводить расчеты для систем с числом частиц до <math>10^9</math>, в зависимости от конкретной задачи. Существует, собственно, всего два классических иерархических алгоритма быстрый мультипольный метод и алгоритм Барнса-Хата. Все остальные в той или иной степени являются их модификациями и комбинациями с другими методами расчета сил.
 +
 
 +
В данной статье рассматривается процесс реализации алгоритма Барнса-Хата на примере двумерного случая.
  
 
= Описание метода =
 
= Описание метода =
 
== Первый этап ==
 
== Первый этап ==
[[Image: Barns2.png|200px|right]]  
+
[[Image: Barns2.png|thumb|210px|right|Пример разбиения иерархического пространства на ячейки для двумерного случая]]  
Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозиции пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответвуют узлам дерева, частицы в них листьям.
+
Объединение частиц в древовидную структуру данных с учетом близости их расположения друг к другу. Существуют реализации с построением дерева путем объединения групп частиц (ближайшие частицы объединяются в пары, образуя узлы, затем пары также объединяются между собой и т.д.). Однако обычно это делается просто иерархической декомпозицией пространства на кубические ячейки. Для двумерного случая пример такого разбиения показан на рисунке справа. Ячейки в нем соответствуют узлам дерева, частицы в них листьям.
  
 
== Второй этап ==
 
== Второй этап ==
 
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме:
 
Для подсчета результирующей силы, действующей на какую-либо произвольно взятую частицу, совершается обход дерева от корня. При достижении очередного узла дальнейший расчет проходит по следующей схеме:
 
<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> - максимальное рассиояние от центра масс ячейки до ее границы, <math>r</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=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) Дерево_(структура_данных)]
  
=='''Ссылки'''==
 
* [[Виртуальная лаборатория]]
 
<br>
 
 
[[Category: Виртуальная лаборатория]]
 
[[Category: Виртуальная лаборатория]]
[[Category: Программирование]]
 
[[Category: JavaScript]]
 

Текущая версия на 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.


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

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


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

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

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