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

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

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

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

FMM также применялся для эффективного рассмотрения кулоновского взаимодействия в методе Хартри-Фока и теории функционала плотности расчетов в квантовой химии .

Набросок алгоритма

В своей простейшей форме метод быстрого мультиполя пытается оценить следующую функцию:

f(y)=\sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y-x_{\alpha }}}

,

где $x_{\alpha }\in [-1,1]$ представляют собой набор шестов и $\phi _{\alpha }\in \mathbb {C}$ соответствующие веса полюсов на множестве точек $\{y_{1},\ldots ,y_{M}\}$ с $y_{\beta }\in [-1,1]$ . Это одномерная форма задачи, но алгоритм можно легко обобщить на несколько измерений и ядра, отличные от $(y-x)^{-1}$ .

Наивно оценивая $f(y)$ на $M$ очков требует ${\mathcal {O}}(MN)$ операции. Важнейшее наблюдение, лежащее в основе метода быстрых мультиполей, заключается в том, что если расстояние между $y$ и $x$ достаточно велик, то $(y-x)^{-1}$ хорошо аппроксимируется полиномом . Конкретно, пусть $-1<t_{1}<\ldots <t_{p}<1$ — чебышёвские узлы порядка $p\geq 2$ и пусть $u_{1}(y),\ldots ,u_{p}(y)$ — соответствующие базисные полиномы Лагранжа . Можно показать, что интерполяционный полином:

{\frac {1}{y-x}}=\sum _{i=1}^{p}{\frac {1}{t_{i}-x}}u_{i}(y)+\epsilon _{p}(y)

быстро сходится с полиномиальным порядком, $|\epsilon _{p(y)}|<5^{-p}$ , при условии, что полюс находится достаточно далеко от области интерполяции, $|x|\geq 3$ и $|y|<1$ . Это известно как «локальная экспансия».

За счет этой интерполяции происходит ускорение метода быстрых мультиполей: при условии, что все полюса находятся «далеко», мы оцениваем сумму только на узлах Чебышева за счет ${\mathcal {O}}(Np)$ , а затем интерполировать его на все нужные точки ценой ${\mathcal {O}}(Mp)$ :

\sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y_{\beta }-x_{\alpha }}}=\sum _{i=1}^{p}u_{i}(y_{\beta })\sum _{\alpha =1}^{N}{\frac {1}{t_{i}-x_{\alpha }}}\phi _{\alpha }

С $p=-\log _{5}\epsilon$ , где $\epsilon$ числовой допуск, общая стоимость равна ${\mathcal {O}}((M+N)\log(1/\epsilon ))$ .

Чтобы гарантировать, что полюса действительно хорошо разделены, единичный интервал рекурсивно разделяется так, что только ${\mathcal {O}}(p)$ полюса оказываются в каждом интервале. Затем используется явная формула внутри каждого интервала и интерполяция для всех хорошо разделенных интервалов. Масштабирование это не портит, так как нужно не более $\log(1/\epsilon )$ уровни в пределах заданного допуска.

См. также

Ссылки

^ Рохлин, Владимир (1985). « Быстрое решение интегральных уравнений классической теории потенциала ». J. Вычислительная физика Том. 60, стр. 187–207.
^ Надер Энгета , Уильям Д. Мерфи, Владимир Рохлин и Мариус Василиу (1992), «Метод быстрых мультиполей для расчета электромагнитного рассеяния», Транзакции IEEE на антеннах и распространении 40, 634–641.
^ «Метод быстрых мультиполей» . Архивировано из оригинала 3 июня 2011 г. Проверено 10 декабря 2010 г.
^ Ципра, Барри Артур (16 мая 2000 г.). «Лучшее в 20 веке: редакторы назвали 10 лучших алгоритмов» . СИАМ Новости . 33 (4). Общество промышленной и прикладной математики : 2 . Проверено 27 февраля 2019 г.

Внешние ссылки

Гибсон, Уолтон К. Метод моментов в электромагнетике (3-е изд.), Chapman & Hall/CRC, 2021. ISBN 9780367365066 .
Аннотация к оригинальной статье Грингарда и Рохлина
Краткий курс быстрых мультипольных методов Рика Битсона и Лесли Грингарда.
JAVA-анимация метода быстрых мультиполей Хорошая анимация метода быстрых мультиполей с различными адаптациями.

Бесплатное программное обеспечение

Puma-EM Высокопроизводительный параллельный код электромагнетизма метода моментов с открытым исходным кодом / многоуровневого быстрого многополюсного метода.
KIFMM3d Независимый от ядра быстрый мультипольный 3d-метод (kifmm3d) — это новая реализация FMM, которая не требует явного расширения мультиполя базового ядра и основана на оценках ядра.
PVFMM Оптимизированная параллельная реализация KIFMM для расчета потенциалов от источников частиц и объемов.
FastBEM Бесплатные программы быстрых мультипольных граничных элементов для решения 2D/3D задач потенциала, упругости, стоксова потока и акустических задач.
FastFieldSolvers поддерживает распространение инструментов FastHenry и FastCap, разработанных в Массачусетском технологическом институте для решения уравнений Максвелла и извлечения паразитов схемы (индуктивности и емкости) с использованием FMM.
ExaFMM ExaFMM — это трехмерный FMM-код с поддержкой CPU/GPU для ядер Лапласа/Гельмгольца, ориентированный на параллельную масштабируемость.
ScalFMM. Архивировано 2 мая 2017 г. на Wayback Machine. ScalFMM — это программная библиотека C++, разработанная в Inria Bordeaux с большим упором на универсальность и распараллеливание (с использованием OpenMP / MPI ).
DASHMM DASHMM — это библиотека программного обеспечения C++, разработанная в Университете Индианы с использованием асинхронной многозадачной системы выполнения HPX-5. Он обеспечивает унифицированное выполнение на компьютерах с общей и распределенной памятью и предоставляет ядра 3D Лапласа, Юкавы и Гельмгольца.
RECFMM Адаптивный FMM с динамическим параллелизмом на многоядерных процессорах.

[1] Рохлин, Владимир (1985). « Быстрое решение интегральных уравнений классической теории потенциала ». J. Вычислительная физика Том. 60, стр. 187–207.

[2] Надер Энгета , Уильям Д. Мерфи, Владимир Рохлин и Мариус Василиу (1992), «Метод быстрых мультиполей для расчета электромагнитного рассеяния», Транзакции IEEE на антеннах и распространении 40, 634–641.

[3] «Метод быстрых мультиполей» . Архивировано из оригинала 3 июня 2011 г. Проверено 10 декабря 2010 г.

[4] Ципра, Барри Артур (16 мая 2000 г.). «Лучшее в 20 веке: редакторы назвали 10 лучших алгоритмов» . СИАМ Новости . 33 (4). Общество промышленной и прикладной математики : 2 . Проверено 27 февраля 2019 г.

[1]

[2]

[3]

[4]