Быстрое преобразование мультиполей (FMM): прорыв в задачах N тел

Гравитация, кулоновские силы и проблема квадратичной сложности

Одной из классических задач вычислительной физики является проблема N тел. Как рассчитать движение миллиардов звезд в галактике под действием взаимной гравитации? Как смоделировать поведение миллионов атомов в белковой молекуле, взаимодействующих через электростатические силы Кулона? Суть проблемы заключается в дальнодействующем характере этих сил. Каждая частица в системе влияет на все остальные частицы, независимо от расстояния между ними.

Если мы попытаемся вычислить силы «в лоб» прямым суммированием, нам придется рассчитать взаимодействие каждой частицы с каждой другой. Это означает, что вычислительная сложность алгоритма растет пропорционально квадрату числа частиц (O(N^2)). Для миллиона частиц потребуется триллион операций на каждом шаге интегрирования по времени. Это абсолютный вычислительный тупик: даже самые мощные суперкомпьютеры не способны моделировать динамику плазмы или формирование галактик в течение приемлемого времени, используя прямые методы расчета.

Идея кластеризации и мультипольное разложение

В 1987 году Владимир Рохлин и Лесли Грингард опубликовали статью, описывающую Быстрое преобразование мультиполей (Fast Multipole Method, FMM). Этот алгоритм был признан журналом Computing in Science & Engineering одним из 10 главных алгоритмов 20 века. FMM радикально снижает сложность задачи N тел с O(N^2) до O(N log N), а в некоторых реализациях — и до строгого O(N).

Идея алгоритма базируется на простом физическом наблюдении: если вы находитесь на Земле, вам не нужно вычислять гравитационное притяжение от каждого отдельного камня на Луне. Вы можете рассматривать Луну как единый точечный объект с суммарной массой, расположенный в ее центре масс. FMM применяет этот принцип иерархически. Пространство разбивается на кубическое дерево (octree в 3D или quadtree в 2D). Частицы, находящиеся близко друг к другу (в соседних ячейках), взаимодействуют напрямую. Но для частиц в далеких кластерах их суммарное гравитационное или электрическое поле заменяется компактным математическим рядом — мультипольным разложением.

Математика сферических гармоник

Вместо того чтобы суммировать миллионы дробей (потенциалов от отдельных точечных зарядов), алгоритм FMM раскладывает потенциал далекого кластера в ряд Тейлора или в ряд по сферическим гармоникам (решениям уравнения Лапласа). Коэффициенты этого ряда (мультипольные моменты — монополь, диполь, квадруполь и т.д.) несут в себе сжатую информацию о распределении масс или зарядов внутри ячейки.

Специальные теоремы сложения позволяют сдвигать центры этих разложений и переводить мультипольные моменты в локальные разложения поля вблизи других кластеров. Таким образом, расчет влияния миллиона частиц на другой миллион далеких частиц сводится к вычислению нескольких десятков мультипольных коэффициентов. FMM произвел революцию не только в астрофизике и молекулярной динамике, но и в вычислительной электродинамике (метод моментов) при расчете эффективной площади рассеяния самолетов (стелс-технологий) и проектировании антенн мобильной связи, сделав возможным моделирование структур размером в сотни длин волн.