Методы декомпозиции областей (Domain Decomposition): параллельные вычисления

Преодоление ограничений памяти и распараллеливание

С развитием суперкомпьютеров вычислительная математика столкнулась с новой, сугубо архитектурной проблемой. Когда мы решаем дифференциальные уравнения в частных производных (УЧП) на сетках, состоящих из десятков миллиардов узлов (например, при расчете глобальной климатической модели Земли или аэродинамики космического корабля в сборе), физически невозможно поместить глобальную матрицу системы в оперативную память одного вычислительного узла. Возникает острая необходимость разрезать гигантскую математическую задачу на тысячи более мелких кусков, раздать их независимым процессорам (или узлам кластера) и заставить эти процессоры общаться между собой по сети MPI для получения единого, математически строгого решения.

Эта концепция легла в основу методов декомпозиции областей (Domain Decomposition Methods, DDM). Идея метода невероятно стара: еще в 1870 году математик Герман Шварц придумал альтернирующий метод для аналитического решения уравнения Лапласа в сложных областях. Он показал, что если сложная область состоит из двух перекрывающихся простых фигур (например, круга и прямоугольника), можно поочередно решать задачу в каждой из них, используя на границе перекрытия значения, полученные у соседа на предыдущем шаге. Спустя сто лет эта абстрактная математическая теорема стала фундаментом параллельных суперкомпьютерных вычислений.

Методы с перекрытием (Метод Шварца) и без перекрытия

Современные численные реализации DDM делятся на две большие группы. Первая группа — это методы с перекрытием (Overlapping methods), прямые наследники классического метода Шварца. Расчетная сетка разбивается на субдомены, которые искусственно расширяются так, чтобы они немного наслаивались друг на друга. Итерационный процесс заключается в том, что каждый процессор решает свою локальную СЛАУ внутри своего домена, а затем пересылает значения из зоны перекрытия соседним процессорам, чтобы те использовали их как краевые условия Дирихле на следующей итерации. Этот метод очень надежен, но пересылка больших массивов данных в зонах перекрытия может замедлять сеть кластера.

Вторая группа — это методы без перекрытия (Non-overlapping methods, или методы подконструкций). Здесь граница между доменами представляет собой строгую математическую линию (или поверхность) толщиной в один узел сетки. Эти методы математически более сложны, так как на общей границе необходимо обеспечить не только непрерывность самой функции (температуры), но и непрерывность нормальной производной (теплового потока). Для этого используются специальные алгоритмы на интерфейсах (например, метод Дирихле-Неймана или метод Неймана-Неймана).

Дополнение Шура и предобуславливание FETI

Самым мощным математическим аппаратом для методов без перекрытия является матричное дополнение Шура (Schur Complement). Алгоритм алгебраически исключает все внутренние узлы каждого субдомена, сводя гигантскую глобальную СЛАУ к гораздо меньшей системе уравнений, которая записана исключительно относительно неизвестных значений на самих интерфейсах (границах разреза). После решения интерфейсной задачи каждый процессор абсолютно независимо и быстро восстанавливает решение внутри своего куска.

Для решения сложной интерфейсной системы обычно применяется метод сопряженных градиентов (CG). Чтобы он сошелся быстро, французский ученый Шарль Фархат разработал знаменитый алгоритм FETI (Finite Element Tearing and Interconnecting), который вводит множители Лагранжа (силы взаимодействия) на границах и использует сложные проекционные предобуславливатели. Сегодня алгоритмы типа FETI-DP (с двумя уровнями грубой сетки) обеспечивают идеальную масштабируемость: программа может эффективно задействовать сотни тысяч процессорных ядер, ускоряя решение пропорционально размеру суперкомпьютера.