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

Быстрый мультипольный метод (БММ) — это численный метод, разработанный для ускорения расчета дальнодействующих сил гравитационной задачи 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 тел

• Октодерево

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