Рекомендации для вложенных прекондиционеров

9

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

  • С одной стороны, вы можете запустить внутреннее решение для конвергенции в каждом шаге внешнего решения.

  • С другой стороны, вы вообще не могли бы выполнить внутреннее решение, а вместо этого заменить его внутренним предварительным кондиционером.

  • Где-то посередине вы можете обрезать внутренний цикл Крылова после некоторого фиксированного числа итераций или после достижения определенного допуска.

Опытным путем я сталкивался с ситуациями, когда первая крайность лучше, и разными ситуациями, когда вторая крайность лучше (с точки зрения общей стоимости). Тем не менее, я не могу найти четкой причины, по которой определенные ситуации предпочитают одну стратегию другой.

Есть ли какое-либо руководство или теория о том, когда эти разные стратегии предпочтительнее?

Ник Алджер
источник
4
По крайней мере, для третьей (промежуточной) ситуации в вашем списке, хорошим местом для начала могут быть Simoncini и Szyld, Гибкие методы внутреннего и внешнего пространства подпространств Крылова, SIAM J. Numer. Анальный. 40 с. 2219-2239.
Эндрю Т. Баркер
Спасибо за ссылку, мне любопытно посмотреть, что у них там. Странно, но на практике я обнаружил, что выполнение различных форм промежуточной ситуации дает худшие результаты. Если номер допуска / итерации фиксирован, внешний решатель имеет тенденцию зависать на уровне ошибки внутреннего допуска. Начинать с большого внутреннего допуска и уменьшать его по мере развития внешнего метода также, похоже, хуже, чем просто устанавливать маленькое внутреннее отклонение с самого начала.
Ник Алджер
Используете ли вы гибкие методы Крылова? Результаты, которые вы описываете, это то, что я ожидал бы, если бы вы не были. Промежуточная ситуация - это как раз та ситуация, когда предобусловливатель (немного) отличается на каждой итерации, когда требуются гибкие методы Крылова.
Эндрю Т. Баркер

Ответы:

1

Этот вопрос был открыт давно, но я думаю, что он все еще заслуживает ответа.

Основная проблема с использованием решателей пространства Крылова на отдельных блоках в качестве внутренних предобусловливателей состоит в том, что они не являются линейными операторами. Чтобы понять это, давайте обозначим черезx~=K(A,P,τ,N;b) вектор, который вы получаете в качестве решения, запустив метод пространства Крылова K на линейной системе Ax=b самое большее N итерации или до допуска τ достигается с помощью предварительного кондиционера PA1, Другими словами, вы можете думать оK как оператор, который действует на b,

Теперь обратите внимание, что K(A,P,0,;) является линейным оператором: это потребует решения Ax=b точно, т.е. K(A,P,0,;b)=A1b, который является линейным в b, Во многих случаях запуск метода пространства Крылова для ровно одной итерации, начиная с нулевого вектора, также является линейным оператором, применяемым кb, Но поскольку последовательность векторов Крылова зависит от начального остаткаr(0)=bAx(0), Оператор K(A,P,τ,N;) вообще не является линейным оператором для конечного N а также τ,

Это означает, что если вы используете K(A,P,τ,N;) как часть предварительного кондиционера для линейной системы, в которой A один блок, то вы получите предварительный кондиционер, который не действует как линейный оператор.

Это противоречит многим другим методам, которые используются для предварительной обработки: например, один шаг SSOR является линейной операцией над вектором, к которому вы его применяете, как и все другие методы, которые применяют один шаг итерации с фиксированной запятой.

Основная проблема теперь состоит в том, что большинство методов пространства Крылова требуют, чтобы предобусловливатель был линейным оператором. Они просто не будут сходиться, если предварительный кондиционер не является линейным, что объясняет ваше наблюдение. С другой стороны, существуют варианты некоторых пространственных методов Крылова - обычно с префиксом слова «Гибкий», таких как F-GMRES в «Гибком GMRES» - которые работают вокруг этого и могут иметь дело с прекондиционерами, которые не являются линейными операторы. Эти гибкие варианты исходных методов будут по-прежнему сходиться и часто являются мощными методами в сочетании с хорошими (но нелинейными) предварительными кондиционерами.

Вольфганг Бангерт
источник