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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

↑ Рохлин, Владимир (1985). « Быстрое решение интегральных уравнений классической теории потенциала» . J. Computational Physics Vol. 60. С. 187–207.
^ Надер Энгет , Уильям Д. Мерфи, Владимир Рохлин , и Marius Vassiliou (1992), «Быстрый метод Multipole для рассеяния электромагнитных волн вычислений,» IEEE Transactions на антеннах и распространении 40, 634-641.
^ "Архивная копия" . Архивировано из оригинала на 2011-06-03 . Проверено 10 декабря 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка )
^ CIPRA, Барри Артур (16 мая 2000). «Лучшее из ХХ века: редакция назвала 10 лучших алгоритмов» . Новости SIAM . Общество промышленной и прикладной математики . 33 (4): 2 . Проверено 27 февраля 2019 года .

Внешние ссылки [ править ]

Гибсон, Уолтон К. Метод моментов в электромагнетизме . Chapman & Hall / CRC, 2008. ISBN 978-1-4200-6145-1
FEKO от Altair HyperWorks включает в себя Многоуровневый FMM как вариант решения.
Serenity Код высокоточного радиолокационного сечения (RCS), который использует метод момента и FMM.
Резюме оригинальной статьи Грингарда и Рохлина.
Краткий курс по быстрым многополюсным методам Рика Битсона и Лесли Грингарда.
JAVA-анимация быстрого многополюсного метода Хорошая анимация быстрого многополюсного метода с различными адаптациями.

Бесплатное программное обеспечение [ править ]

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

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

[2] Надер Энгет , Уильям Д. Мерфи, Владимир Рохлин , и Marius Vassiliou (1992), «Быстрый метод Multipole для рассеяния электромагнитных волн вычислений,» IEEE Transactions на антеннах и распространении 40, 634-641.

[3] "Архивная копия" . Архивировано из оригинала на 2011-06-03 . Проверено 10 декабря 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка )

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

[1]