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

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

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

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

См. также

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

• Октодерево

Ссылки

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