Быстрый метод мультиполей

Быстрый мультипольный метод (БММ) — это численный метод, разработанный для ускорения расчета дальнодействующих сил в гравитационной задачи n-тел. Ускорение достигается за счёт представления функции Грина^[англ.] в виде мультипольного разложения, которое позволяет группировать источники сил, расположенные близко друг к другу, и обрабатывать их, как если бы они были одним источником силы.^[1]

БММ также применяется для ускорения итерационного решения в методе граничного элемента применительно к вычислительным задачам электромагнетизма.^[2] БММ был впервые представлен Лесли Грингардом и Владимиром Рохлиным^[3] и основывался на мультипольном разложении векторного уравнения Гельмгольца. Посредством обработки взаимодействий между удаленными базовыми функциями с использованием БММ соответствующие элементы матрицы не нужно хранить, что приводит к значительному сокращению требуемой памяти. Если применять БММ иерархически, это может улучшить сложность алгоритма в итеративном подходе от ${\displaystyle {\mathcal {O}}(N^{2})}$ до ${\displaystyle {\mathcal {O}}(N)}$, то есть, при заданной погрешности ${\displaystyle \varepsilon }$, произведение матрицы на вектор гарантированно находится в пределах погрешности ${\displaystyle \varepsilon .}$ Если рассчитать зависимость сложности от допуска ${\displaystyle \varepsilon }$, то получится ${\displaystyle {\mathcal {O}}(\log(1/\varepsilon ))}$, что делает итоговую сложность алгоритма ${\displaystyle {\mathcal {O}}(\log(1/\varepsilon )N)}$. Это расширяет область применения БММ до большего количества задач.

БММ считается одним из десяти лучших алгоритмов 20-го века.^[4] Данный метод уменьшает сложность умножения матрицы на вектор с использованием определенного типа плотной матрицы, которая возникает во многих физических системах.

См. также

• Гравитационная задача N тел

• Октодерево

Ссылки

• Быстрый Метод Мультиполей, Гумеров Н.А,

Примечания

1. V Rokhlin. Rapid solution of integral equations of classical potential theory (англ.) // Journal of Computational Physics. — 1985-09-15. — Vol. 60, iss. 2. — P. 187–207. — ISSN 0021-9991. — doi:10.1016/0021-9991(85)90002-6. Архивировано 4 апреля 2019 года.
2. Eric Darve. The Fast Multipole Method: Numerical Implementation (англ.) // Journal of Computational Physics. — 1999. — № 160. — С. 195—240. Архивировано 6 ноября 2020 года.
3. The Fast Multipole Method  (неопр.). web.archive.org (3 июня 2011). Дата обращения: 8 марта 2020. Архивировано 3 июня 2011 года.
4. SIAM: The Best of the 20th Century: Editors Name Top 10 Algorithms  (неопр.). archive.siam.org. Дата обращения: 8 марта 2020. Архивировано 20 сентября 2018 года.