Методы N-тел и «частица-сетка»

Вычисление взаимных гравитационных или электростатических сил между множеством частиц наивным способом требует затрат, пропорциональных квадрату их числа. Быстрые методы N-тел и «частица-сетка» сокращают эти затраты почти до линейных, что делает возможным моделирование галактик и плазмы с миллионами частиц.

Definition

Методы N-тел и «частица-сетка» — это алгоритмы, которые аппроксимируют дальнодействующие силы между множеством взаимодействующих частиц за время менее квадратичного путем группировки удаленных частиц или решения поля на сетке.

Scope

Эта тема охватывает масштабируемые алгоритмы для дальнодействующих взаимодействий частиц: иерархические древовидные коды, такие как Барнса-Хата, метод быстрых мультиполей, а также сеточные схемы «частица-сетка» и «частица-частица-сетка». Рассматриваются компромиссы между точностью и стоимостью, а также роль этих методов в крупномасштабных гравитационных и электростатических симуляциях.

Core questions

• Почему прямое суммирование попарных дальнодействующих сил является непомерно дорогим?
• Как древовидные коды группируют удаленные частицы для снижения стоимости вычисления сил?
• Как метод быстрых мультиполей достигает почти линейной масштабируемости с контролируемой ошибкой?
• Как методы «частица-сетка» решают поле на сетке для обработки дальнодействующих сил?

Key theories

Иерархические древовидные коды

Алгоритм Барнса-Хата группирует удаленные частицы в ячейки, коллективная сила которых аппроксимируется их центром масс, сокращая стоимость вычисления сил с квадратичной до порядка N log N.

Метод быстрых мультиполей

Метод быстрых мультиполей представляет группы частиц усеченными мультипольными разложениями и иерархически их транслирует, достигая почти линейной масштабируемости со строго контролируемой точностью.

Методы «частица-сетка»

Схемы «частица-сетка» и «частица-частица-сетка» интерполируют заряды или массы на сетку, решают поле с помощью быстрых преобразований Фурье и добавляют короткодействующие поправки, эффективно обрабатывая дальнодействующие взаимодействия.

Clinical relevance

Эти методы используются в космологических и галактических N-тельных симуляциях формирования структур, в моделировании плазмы и в расчетах дальнодействующей электростатики больших молекулярных систем. Метод быстрых мультиполей признан одним из важнейших алгоритмов двадцатого века.

History

Методы «частица-сетка» были систематизированы Хокни и Иствудом в 1980-х годах; древовидный код Барнса-Хата 1986 года и метод быстрых мультиполей Греенгарда и Рохлина 1987 года преобразовали N-тельные симуляции, сделав возможными последующие крупномасштабные космологические и молекулярные симуляции.

Key figures

• Josh Barnes
• Piet Hut
• Leslie Greengard
• Vladimir Rokhlin

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

Почему бы просто не вычислять каждую попарную силу напрямую?

Затраты на прямое суммирование растут как квадрат числа частиц, поэтому удвоение числа частиц учетверяет объем работы, что становится невозможным для миллионов или миллиардов частиц в космологических и крупномасштабных молекулярных симуляциях. Быстрые методы сокращают эти затраты почти до линейных.

Как древовидные и мультипольные методы контролируют свою ошибку?

Они аппроксимируют влияние удаленных групп частиц, и аппроксимация уточняется путем включения большего числа мультипольных членов или использования более строгого критерия открытия, что позволяет контролируемо балансировать между точностью и скоростью.