Многосеточные методы (Multigrid): масштабируемое решение сверхбольших СЛАУ
Иерархия сеток для победы над вычислительной сложностью
При решении эллиптических дифференциальных уравнений в частных производных (например, уравнения Пуассона для электростатического потенциала или давления в гидродинамике) возникают огромные системы линейных алгебраических уравнений. Мы уже упоминали методы подпространств Крылова, которые отлично справляются с этой задачей. Однако существует класс алгоритмов, который математически превосходит их по масштабируемости, достигая теоретического предела вычислительной эффективности — линейной сложности O(N). Это многосеточные методы (Multigrid methods, MG).
Проблема традиционных итерационных методов (таких как метод Гаусса-Зейделя) заключается в том, что они обладают отличным свойством сглаживания (smoothing). Они мгновенно убивают высокочастотные колебания ошибки (осцилляции на уровне соседних узлов сетки). Но низкочастотные компоненты ошибки (глобальные волны, растянутые на всю расчетную область) эти методы подавляют мучительно долго. Именно поэтому алгоритм вначале сходится быстро, а затем «зависает», требуя тысяч итераций для устранения длинноволновых погрешностей.
Переход между масштабами: сужение и продолжение
Идея многосеточных методов гениальна в своей простоте: то, что является длинноволновой (низкочастотной) ошибкой на мелкой сетке, становится коротковолновой (высокочастотной) ошибкой на более крупной сетке! Алгоритм работает с целой иерархией вложенных сеток — от самой мелкой до очень грубой.
Процесс начинается на мелкой сетке. Метод Гаусса-Зейделя делает несколько итераций, быстро сглаживая ошибку (высокочастотный шум). Оставшаяся плавная ошибка (невязка) переносится на более грубую сетку с помощью математического оператора сужения (restriction). На грубой сетке эта ошибка кажется «острой», и сглаживатель снова эффективно ее давит. Этот процесс погружения продолжается вплоть до самой грубой сетки (состоящей из десятка узлов), где СЛАУ решается точно прямым методом практически мгновенно. Затем найденная поправка возвращается обратно на мелкие сетки через оператор интерполяции или продолжения (prolongation), корректируя решение на каждом уровне.
V-циклы, W-циклы и алгебраический многосеточный метод (AMG)
Последовательность спусков на грубые сетки и подъемов на мелкие формирует так называемые циклы. Самый популярный из них — V-цикл (вниз и вверх). Существуют также W-циклы, которые проводят больше времени на грубых уровнях для лучшей очистки от низкочастотных ошибок, и F-циклы (Full Multigrid), которые вообще начинают работу с самой грубой сетки, постепенно переходя к точным вычислениям на мелких.
Классический геометрический многосеточный метод требует явного знания геометрии расчетной области для построения грубых сеток, что трудно реализовать для деталей со сложной криволинейной границей. Поэтому в современных промышленных пакетах (ANSYS, COMSOL) применяется Алгебраический Многосеточный Метод (AMG). Он строит иерархию сеток и операторы перехода не на основе геометрических координат узлов, а исключительно на основе значений коэффициентов в самой матрице СЛАУ. AMG работает как мощный черный ящик (или предобуславливатель для метода сопряженных градиентов), обеспечивая сверхбыстрое решение систем с миллиардами уравнений на суперкомпьютерах.