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

БММ также применяется для ускорения итерационного решения в методе граничного элемента применительно к вычислительным задачам электромагнетизма. БММ был впервые представлен Лесли Грингардом и Владимиром Рохлиным и основывался на мультипольном разложении векторного уравнения Гельмгольца. Посредством обработки взаимодействий между удаленными базовыми функциями с использованием БММ соответствующие элементы матрицы не нужно хранить, что приводит к значительному сокращению требуемой памяти. Если применять БММ иерархически, это может улучшить сложность алгоритма в итеративном подходе от ${\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-го века. Данный метод уменьшает сложность умножения матрицы на вектор с использованием определенного типа плотной матрицы, которая возникает во многих физических системах.

См. также

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

• Октодерево

Ссылки

Примечания