Метод Барнса-Хата

Аннотация

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

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

Первый этап

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