Можно ли использовать метод подпространств Крылова как сглаживатель для многосетки?

15

Насколько мне известно, многосеточные решатели используют итеративные сглаживатели, такие как Якоби, Гаусс-Зайдель и SOR, чтобы смягчить ошибку на различных частотах. Можно ли использовать метод подпространств Крылова (например, сопряженный градиент, GMRES и т. Д.)? Я не думаю, что они классифицируются как «сглаживатели», но их можно использовать для аппроксимации решения с грубой сеткой. Можем ли мы ожидать аналогичной сходимости к решению, как в стандартном многосеточном методе? Или это зависит от проблемы?

Пол
источник

Ответы:

18

Да, можно, но методы Крылова, как правило, не обладают хорошими сглаживающими свойствами. Это потому, что они нацелены на весь спектр адаптивным способом, который минимизирует остаточную или подходящую норму ошибки. Как правило, это будет включать в себя некоторые низкочастотные (длинноволновые) моды, с которыми грубые сетки могли бы нормально работать. Сглаживатели Крылова также делают многосеточный цикл нелинейным, поэтому, если мультисетка используется в качестве предварительного условия для внешнего метода Крылова, внешний метод должен быть «гибким» (например, GCR или FGMRES).

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

Более популярной альтернативой является использование полиномиальных сглаживателей (обычно чебышевских). Эти методы нацелены на указанную часть спектра. Для симметричных эллиптических уравнений в частных производных (где дискретный оператор является симметричным положительно определенным или почти таковым), обычно оценивают наибольшее собственное значение из где D ^ {- 1} - это точечный блок Предобработчик Якоби для A и целевой диапазон, например (0.1 \ lambda _ {\ max}, 1.1 \ lambda _ {\ max}) . Полиномиальные сглаживатели не имеют сокращений и являются линейными операциями (для любой выбранной степени полинома, обычно выбираемой между 1 и, возможно, 5 ). Обычно несколько итераций (скажем, от 5 до 10)λМаксимумD-1AD-1A(0,1λМаксимум,1,1λМаксимум)15510) GMRES или CG используются для оценки λМаксимум , поэтому пользователю не нужно вычислять их самостоятельно. Оценка λМаксимум также используется некоторыми алгебраическими многосеточными методами для выбора стратегий укрупнения.

Адамс, Брезина, Ху и Туминаро (2003) - хорошая статья о параллельной и алгоритмической производительности полиномиальных сглаживателей. Обратите внимание, что полиномиальные сглаживатели имеют тенденцию быть менее эффективными (и / или трудными для формулировки) для несимметричных задач, и в этом случае вы, вероятно, захотите использовать метод Гаусса-Зейделя или более сложные (блочные / распределенные) схемы релаксации.

Джед браун
источник
Можете ли вы предложить хороший ресурс по полиномиальным и / или крыловым сглаживателям? Я на самом деле никогда не слышал об этом :)
Пол
@JedBrown: Вы имеете в виду «эллиптический» в смысле PDE или билинейной формы (т. Е. Подразумеваете ли вы, что все собственные значения оператора или главного символа положительны?)? Я предполагаю последнее, так как вы говорите о точечном блоке Якоби.
Джек Полсон
Павел I добавил ссылку. @ Джек Строго говоря, дискретный оператор должен быть SPD, но на практике методы имеют тенденцию работать, пока спектр не слишком плохо распределен.
Джед Браун