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

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

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

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

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

Смотрите также

• Моделирование Barnes – Hut
• Многополюсное расширение
• пмоделирование тела

Рекомендации

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

внешняя ссылка

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

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

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