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

Абрамова О.А., Иткулова Ю.А., Марьин Д.Ф., Малышев В.Л., Моисеева Е.Ф., Гумеров Н.А.

Все задачи, решаемые в лаборатории современного компьютерного моделирования микро- и наномасштабных процессов, объединены единым подходом или центральным методом решения, который развивается в лаборатории, а именно, быстрый метод мультиполей (БММ, англ. - Fast Multipole Method, FMM).

БММ был изначально разработан американскими учеными Рохлиным и Грингардом (Rokhlin & Greengard) в середине 80-х прошлого столетия и предназначался для быстрого вычисления гравитационного потенциала в задаче N тел и, по оценке экспертов, наряду с такими алгоритмами как быстрое преобразование Фурье, вошел в десятку лучших алгоритмов 20-го столетия. Известно, что точное нахождение потенциала взаимодействия для N тел требует порядка N2 операций. Предложенный алгоритм решает эту задачу используя всего kN операций, где k много меньше чем N. Для больших N это позволяет ускорить вычисления в тысячи раз и решать проблемы, которые просто было бы невозможно решить с помощью стандартного алгоритма. Отличие БММ от другого революционного алгоритма, быстрого преобразования Фурье состоит в том, что для быстрого преобразования Фурье все данные (скажем, тела) должны быть расположены на равномерной сетке, что, конечно, не так для произвольного расположения звезд, атомов, или других объектов, в то время как БММ может применяться для произвольного (неструктурированного) множества.

Иерархическая структура быстрого метода мультиполей

БММ достигает своей цели за счет использования иерархической структуры данных и математической теории разложения и трансляции функций, что делает его относительно непростым, как для понимания, так и для эффективной реализации. Возможно, по этой или другим причинам в России БММ не получил надлежащего развития. В то же время, в мире (США, Японии, Европе) за последние два десятилетия были достигнуты впечатляющие результаты с использованием БММ, как почти универсального метода для численного решения задач математической физики, включая течения жидкости, акустику, электромагнетизм, молекулярную динамику и многое другое. Универсальность метода обусловлена тем, что классические линейные и нелинейные задачи сводятся к решению больших плотных систем уравнений, которые и составляют основную вычислительную проблему (скажем, могут потреблять до 99% всех вычислительных ресурсов) и ускорение решения имеет первостепенную важность. Масштаб современных проблем, решаемых при прямом моделировании, основанном на «первых» принципах (вычисление парных сил в системах с миллионами молекул или же решение уравнений Навье-Стокса в областях со сложными границами, например, создаваемыми тысячами частиц произвольной формы) таков, что придает методам, таким как БММ, особую значимость.

Сравнение времени моделирования одного временного шага динамики молекул воды с/без использования быстрого метода мультиполей (FMM), с/без использования графического процессора (GPU)

Несмотря на короткий срок с момента создания, лаборатория, по сути, является пионером и лидером в области БММ в России и ведет исследования с использованием этого метода на мировом уровне. Для сотрудников лаборатории прочитан курс по БММ, разработанный в Институте передовых компьютерных исследований университета штата Мэриленд (США) и они прошли сертификацию. Впервые в мире в лаборатории был внедрен БММ для прямого расчета динамики деформируемых капель в стоксовом режиме и получены результаты для систем более чем с десятью тысячами капель, задаче, где на каждом шаге по времени требуется решать плотную алгебраическую систему более чем с миллионом неизвестных. БММ также используется для быстрого расчета электростатического потенциала в системах с большим количеством полярных молекул. В настоящее время идет разработка применения БММ для прямого расчета самоорганизации пузырьков в акустических полях. Кроме того, в лаборатории проводятся исследования по реализации параллельных версий БММ на гетерогенных архитектурах содержащих графические процессоры. Первые полученные результаты в этом направлении весьма впечатляющие и уже внедрены в пакеты программ для расчетов динамики эмульсий и молекулярной динамики. Эти результаты докладывались как на всероссийских, так и международных конференциях, включая ICNMMF (International Conference on Numerical Methods in Mechanics of Multiphase Flows, Pennsylvania, USA, June 12-14, 2012) и ASME’2012 (Congress of American Society of Mechanical Engineers, Texas, USA, November 9-15, 2012) и получили высокую международную оценку.