Как мотивирован Krylov Multigrid (с использованием MG в качестве предварительного кондиционера)?

13

Мультисетка (MG) может использоваться для решения линейной системы путем построения начального предположения x 0 и повторения следующего для i = 0 , 1 .. до сходимости:AИксзнак равнобИкс0язнак равно0,1 ..

  1. Вычислить остаток рязнак равноб-AИкся
  2. Нанесите многосеточный цикл , чтобы получить приближение , где е я = г я .ΔИксяеяAеязнак равноря
  3. Обновить Икся+1Икся+ΔИкся

Многосеточный цикл представляет собой некоторую последовательность операций сглаживания, интерполяции, ограничения и точного грубого сеточного решения, применяемых к для получения Δ x i . Обычно это V-цикл или W-цикл. Это линейная операция , поэтому мы написать Δ х я = Б г я .ряΔИксяΔИксязнак равноВря

Можно интерпретировать этот процесс как предварительную итерацию Ричардсона. То есть мы обновляем .Икся+1Икся+Вря

Итерация Ричардсона является прототипом метода подпространств Крылова, в котором предлагается использовать многосеточные циклы для предварительной обработки других методов подпространств Крылова. Это иногда называют «ускоряющей» многосеткой с помощью метода Крылова, или альтернативно можно рассматривать как выбор предобусловливателя для метода Крылова.

Другой способ расширить описанный выше алгоритм - использовать Full Multigrid (FMG). Смотрите этот ответ для краткого описания.

В каких ситуациях MG с крыловым ускорением предпочтительнее MG или FMG?

Патрик Санан
источник
2
(F) MG довольно чувствителен, если один режим не будет должным образом демпфирован плавной или двухуровневой коррекцией, все зависнет. Метод Крылова может помочь смягчить эти проблемные режимы. Так что, насколько я понимаю, это в основном обусловлено надежностью.
Крис

Ответы:

10

В некоторых случаях (F) MG предоставляет алгоритм с оптимальными свойствами. Например, правильно настроенный FMG может решить некоторые эллиптические задачи в небольшом количестве «рабочих единиц», где рабочая единица определяется как вычислительное усилие, необходимое для выражения самой проблемы - в этом случае операции по формированию остаточного на мелкой сетке. Это настолько эффективный (и, следовательно, сложный) алгоритм, который является основой для теста HPC, предназначенного для измерения максимальной производительности суперкомпьютера для решения задач реалистичной физики ( HPGMG ). Если такой метод доступен, то, конечно, целесообразно использовать его.б-AИкс

Однако во многих практических случаях оптимальный или эффективный многосеточный метод не используется. Это может быть потому, что

  • такой метод неизвестен или недоступен для данной проблемы
  • сглаживающие и межсеточные операторы недостаточны для обеспечения конвергенции учебников
  • грубый решатель сетки неточен

ВA

Обратите внимание, что выбор использования неоптимального метода может привести к гораздо «более дешевому» многосеточному циклу до такой степени, что ускорение Крылова окупается. То есть могут быть проблемы (и вычислительные системы), в которых MG с ускорением по Крылову может превзойти MG. Мне было бы интересно найти конкретный пример этого.

(Спасибо @chris выше и Мэтту Кнепли, который упомянул некоторые из вышеперечисленных в учебнике)

Патрик Санан
источник