Проблемы, когда градиент сопряжения работает намного лучше, чем GMRES

17

Меня интересуют случаи, когда градиент сопряжения работает намного лучше, чем метод GMRES.

Вообще, CG является предпочтительным выбором во многих случаях SPD (симметрично-положительно определенного), потому что он требует меньшего объема памяти и теоретическая оценка скорости сходимости для CG вдвое больше, чем GMRES. Есть ли проблемы, когда такие показатели действительно наблюдаются? Есть ли какая-либо характеристика случаев, когда GMRES работает лучше или сравнимо с CG для того же числа spmvs (редкие умножения матрицы на вектор).

linear-solver conjugate-gradient gmres piyush_sao
источник

8

Одна вещь, которую CG имеет в свою пользу, это то, что она не минимизирует дискретную норму $l^2$ для своих остаточных полиномов (что делает GMRES). Вместо этого она сводит к минимуму матрично-индуцированную норму, и очень часто эта матрично-индуцированная норма оказывается очень близкой к энергетической норме для дискретизации физических задач, и зачастую это гораздо более разумная норма для измерения погрешности из-за появления свойств сохранения из физики.

На самом деле вы можете добиться такого же эффекта и с GMRES, если выполнение факторизации массива Холецкого не слишком дорого, вы можете заставить внутренние продукты быть энергетическими внутренними продуктами, которые вы хотите.

Тогда случаи, когда следует ожидать, что CG будет работать совершенно иначе, чем GMRES, - это когда константы, подразумеваемые в эквивалентности норм, сильно отличаются. Это может быть справедливо, например, в методе спектрального Галеркина высокого порядка, где дискретная норма $l^2$ используемая в GMRES, рассматривает все степени свободы как равные, когда в действительности полиномиальные градиенты являются самыми острыми вблизи границ (следовательно, кластеризация узлов), и поэтому константы эквивалентности нормы между этой нормой и, скажем, непрерывной нормой $L^2$ задаваемой матрицей масс, могут быть очень большими.

Reid.Atcheson
источник

Хотел привести здесь пример с методом высокого порядка и историями сходимости CG, GMRES и GMRES + трюк Холецкого ... но, к сожалению, единственный код, который у меня есть для задач второго порядка, это DG несимметричного многообразия .. так что CG isn неприменимо, хотелось бы увидеть это в действии.

Reid.Atcheson

3

Я думаю, что ваш ответ на что-то важное, но я хотел бы, чтобы вы уточнить. В частности, этот вопрос является вопросом чисто линейной алгебры, а ваш ответ говорит о физических нормах, массовых матрицах и т. Д. Из числового уравнения в частных производных. Можем ли мы сказать что-то точное о том, как минимизация в разных нормах в одном и том же пространстве Крылова приводит к различным итерациям?

Эндрю Т. Баркер

Помимо числовых примеров, я не думаю, что было проведено тщательное теоретическое исследование, объясняющее, как разные нормы дают существенно разные ответы. Я думаю, что проблема заключается в том, что результаты вращаются вокруг асимптотики, и для фиксированной линейной системы теоретические результаты будут идентичны по модулю постоянных факторов. Если есть какие-то теоретические исследования, я бы хотел их увидеть, но, спросив у некоторых экспертов по численной линейной алгебре в моем отделе, кажется, что пока нет точного теоретического анализа, показывающего, что происходит с различными нормами.

Reid.Atcheson

4

Я подозреваю, что вообще нет большой разницы между GMRES и CG для матрицы SPD.

Скажем , мы решаем с симметричным положительно определенным и исходным предположением и порождающей итерацией с CG и GMRES, назовем их и . Оба итерационных метода будут строить $Ax = b$ $A$ $x_0 = 0$ $x_k^c$ $x_k^g$ из одного и того же пространства Крылова . Они будут делать это по-разному. $x_k$ $K_k = \{ b, Ab, A^2b, \ldots \}$

CG характеризуется минимизацией ошибки в энергетической норме, индуцированной , так что $e_k^c = x - x_k^c$ $A$

(A е_{К}^{с}, е_{К}^{с}) знак равно (A (Икс - {Икс}_{К}^{с}), Икс - {Икс}_{К}^{с}) знак равно \underset{Y \in К}{мин} (A (Икс - Y), Икс - Y),

$\begin{equation} (A e_k^c, e_k^c) = (A (x - x_k^c), x - x_k^c) = \min_{y \in K} (A (x-y), x-y). \end{equation}$

GMRES минимизирует вместо этого невязку и делает это в дискретной норме , так что $r_k = b - A x^g_k$ $\ell^2$

(р_{К}, р_{К}) знак равно (б - A {Икс}_{К}^{грамм}, б - A {Икс}_{К}^{грамм}) знак равно \underset{Y \in К}{мин} (б - A Y, б - A Y),

$\begin{equation} (r_k, r_k) = (b - A x_k^g, b - A x_k^g) = \min_{y \in K} (b - Ay, b - Ay). \end{equation}$ Теперь, используя уравнение ошибки

мы также можем записать GMRES как минимизирующее

где Я хочу подчеркнуть , что это справедливо только для СПД матрицы

. Тогда мы имеем CG минимизировать ошибку относительно

A e_{k} = r_{k}

$A e_k = r_k$

(р_{К}, р_{К}) знак равно (A е_{К}^{грамм}, A е_{К}^{грамм}) знак равно (A^{2} е_{К}^{грамм}, е_{К}^{грамм})

$\begin{equation} (r_k, r_k) = (A e_k^g, A e_k^g) = (A^2 e_k^g, e_k^g) \end{equation}$

A

$A$

A

$A$ норма и GMRES минимизируют ошибку по отношению к норме

. Если мы хотим, чтобы они вели себя по-разному, интуитивно нам понадобился бы такой

, чтобы эти две нормы были очень разными. Но для SPD

эти нормы будут вести себя совершенно аналогично.

A^{2}

$A^2$

A

$A$

A

$A$

Чтобы быть еще более конкретным, на первой итерации с пространством Крылова и CG, и GMRES построят приближение вида . CG выберет $K_1 = \{ b \}$ $x_1 = \alpha b$

α знак равно \frac{(б, б)}{(A б, б)}

$\begin{equation} \alpha = \frac{ (b,b) }{ (Ab,b) } \end{equation}$

α знак равно \frac{(A б, б)}{(A^{2} б, б)},

$\begin{equation} \alpha = \frac{ (Ab,b) }{ (A^2b,b) }. \end{equation}$

A

$A$

(ϵ, 1, 1, 1, \dots)

$(\epsilon,1,1,1,\ldots)$

b = (1, 1, 0, 0, 0, \dots)

$b = (1,1,0,0,0,\ldots)$

ϵ \to 0

$\epsilon \rightarrow 0$

A

$A$

b

$b$ так что этот коэффициент двух различий сохраняется на протяжении всей итерации, но я сомневаюсь, что он станет еще хуже.

Эндрю Т. Баркер
источник

2

b = (1, \sqrt{ϵ}, 0, 0, \dots)

$b = (1,\sqrt{\epsilon},0,0,\dotsc)$

| b | = \sqrt{1 + ϵ}

$|b| = \sqrt{1 + \epsilon}$

b^{T} A b = \sqrt{2} ϵ

$b^T A b = \sqrt{2} \epsilon$

b^{T} A^{2} b = ϵ \sqrt{1 + ϵ^{2}}

$b^T A^2 b = \epsilon \sqrt{1 + \epsilon^2}$

α_{CG} = \frac{ϵ^{- 1} + 1}{\sqrt{2}} \sim ϵ^{- 1}

$\alpha_{\text{CG}} = \frac{\epsilon^{-1}+1}{\sqrt 2} \sim \epsilon^{-1}$

α_{GMRES} = \sqrt{\frac{2}{1 + ϵ^{2}}} \sim \sqrt{2}

$\alpha_{\text{GMRES}} = \sqrt{\frac{2}{1 + \epsilon^2}} \sim \sqrt{2}$

ϵ^{- 1}

$\epsilon^{-1}$

Джед Браун

3

Одна вещь состоит в том, что GMRES никогда не используется везде, где может применяться CG. Я не думаю, что имеет смысл сравнивать эти два. Для матриц SPD CG определенно является победителем из-за требований к хранилищу и причин, упомянутых выше. Вопрос, который был бы интересен, состоит в том, чтобы найти расширение CG, которое применимо к задачам, где CG не может быть применен. Существуют такие методы, как BiCG-stab, которые не требуют линейного увеличения памяти, такие как GMRES, но конвергенция не так хороша, как GMRES (иногда даже с перезапущенным GMRES).

user1964178
источник

2

Существуют схемы IDR, которые устраняют разрыв между GMRES и BiCG с точки зрения экономии памяти, стабильности и конвергенции: ta.twi.tudelft.nl/nw/users/gijzen/IDR.html Я не уверен, что согласен с тем, что GMRES не следует использовать, если CG может быть. Если вы можете выполнить холеристскую факторизацию матрицы, которая индуцирует вашу энергетическую норму, то вы можете ввести это в симметричную итерацию Ланцоша и получить трехчастичное рекуррентное решение, которое будет вести себя почти как CG. Конечно, CG - более простой вариант, но он доступен :)

Reid.Atcheson

2

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

Джед Браун

Проблемы, когда градиент сопряжения работает намного лучше, чем GMRES

Ответы: