Probleme, bei denen Conjugate gradient viel besser funktioniert als GMRES

17

Ich interessiere mich für Fälle, in denen der Gradient des Konjugats viel besser funktioniert als die GMRES-Methode.

Im Allgemeinen ist CG in vielen Fällen von SPD (Symmetric-Positive-Definite) die bevorzugte Wahl, da es weniger Speicherplatz benötigt und die theoretische Konvergenzrate für CG doppelt so hoch ist wie für GMRES. Gibt es irgendwelche Probleme, bei denen solche Raten tatsächlich beobachtet werden? Gibt es eine Charakterisierung für Fälle, in denen GMRES bei gleicher Anzahl von spmvs eine bessere oder mit CG vergleichbare Leistung erbringt (spärliche Matrix-Vektor-Multiplikationen)?

linear-solver conjugate-gradient gmres piyush_sao
quelle

8

Eine Sache, die CG zu seinen Gunsten hat, ist, dass sie die diskrete $l^2$ -Norm für ihre Restpolynome nicht minimiert (was GMRES tut). Stattdessen wird eine matrixinduzierte Norm minimiert, und sehr oft kommt diese matrixinduzierte Norm der Energienorm für die Diskretisierung physikalischer Probleme sehr nahe, und häufig ist dies eine viel vernünftigere Norm, um Fehler zu messen, da Konservierungseigenschaften auftreten aus der Physik.

Sie können diese Art von Effekt auch mit GMRES erzielen, wenn die Cholesky-Faktorisierung einer Massenmatrix nicht zu teuer ist. Sie können die inneren Produkte dazu zwingen, die inneren Energieprodukte zu sein, die Sie möchten.

Die Fälle, in denen man erwarten sollte, dass CG sich sehr von GMRES unterscheidet, sind dann, wenn die in der Normäquivalenz implizierten Konstanten sehr unterschiedlich sind. Dies kann zum Beispiel bei einer Spektral-Galerkin-Methode hoher Ordnung der Fall sein, bei der die in GMRES verwendete diskrete $l^2$ -Norm alle Freiheitsgrade als gleich behandelt, wenn in Wirklichkeit Polynomgradienten in der Nähe der Grenzen am schärfsten sind (daher Knoten-Clustering), und so weiter Normäquivalenzkonstanten zwischen dieser Norm und der durch die Massenmatrix gegebenen kontinuierlichen $L^2$ -Norm können sehr groß sein.

Reid. Atcheson
quelle

Wollte hier ein Beispiel mit einer Methode hoher Ordnung und Konvergenzverläufen von CG, GMRES und GMRES + Cholesky-Trick geben. Leider ist DG der unsymmetrische Code, den ich für Probleme zweiter Ordnung zur Verfügung habe trifft nicht zu, würde das gerne in Aktion sehen.

Reid.Atcheson

3

Ich denke, Ihre Antwort kommt auf etwas Wichtiges, aber ich wünschte, Sie würden es klarstellen. Insbesondere handelt es sich bei der Frage um eine reine lineare Algebrafrage, und Ihre Antwort bezieht sich auf physikalische Normen und Massenmatrizen usw. aus einer numerischen PDE. Können wir etwas genaues darüber sagen, wie die Minimierung in verschiedenen Normen innerhalb desselben Krylov-Raums zu unterschiedlichen Iterationen führt?

Andrew T. Barker

Abgesehen von numerischen Beispielen glaube ich nicht, dass es bisher eine sorgfältige theoretische Studie gegeben hat, die erklärt, wie unterschiedliche Normen wesentlich unterschiedliche Antworten liefern. Ich denke, das Problem ist, dass sich die Ergebnisse um Asymptotik drehen, und für ein festes lineares System sind die theoretischen Ergebnisse identische Modulo-Konstanten-Faktoren. Wenn es theoretische Studien gibt, würde ich sie gerne sehen, aber nachdem ich einige der Experten für numerische lineare Algebra in meiner Abteilung befragt habe, scheint es noch keine genaue theoretische Analyse zu geben, die zeigt, was mit verschiedenen Normen passiert.

Reid.Atcheson

4

Ich vermute, dass es im Allgemeinen keinen großen Unterschied zwischen GMRES und CG für eine SPD-Matrix gibt.

Nehmen wir an, wir lösen mit symmetrisch positiv definit und die Anfangsschätzung und erzeugen Iterationen mit CG und GMRES, nennen sie und . Beide iterativen Methoden bauen aus demselben Krylov-Raum auf . Sie werden dies auf etwas andere Weise tun. $Ax = b$ $A$ $x_0 = 0$ $x_k^c$ $x_k^g$ $x_k$ $K_k = \{ b, Ab, A^2b, \ldots \}$

$e_k^c = x - x_k^c$ $A$

(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) .

$\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 minimiert stattdessen den Rest und tut dies in der diskreten Norm, so dass Mit der wir nun auch GMRES als Minimierung schreiben. wobei ich betonen möchte, dass dies nur für eine SPD-Matrix . Dann haben wir CG, um den Fehler in Bezug auf die Norm zu minimieren, und GMRES, um den Fehler in Bezug auf die minimieren $r_k = b - A x^g_k$ $\ell^2$

(r_{k}, r_{k}) = (b - A x_{k}^{g}, b - A x_{k}^{g}) = min_{y \in K} (b - A y, b - 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}$

A e_{k} = r_{k}

$A e_k = r_k$

(r_{k}, r_{k}) = (A e_{k}^{g}, A e_{k}^{g}) = (A^{2} e_{k}^{g}, e_{k}^{g})

$\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$

A^{2}

$A^2$ Norm. Wenn wir wollen, dass sie sich sehr unterschiedlich verhalten, brauchen wir intuitiv ein so dass diese beiden Normen sehr unterschiedlich sind. Für SPD verhalten sich diese Normen jedoch ziemlich ähnlich.

A

$A$

A

$A$

Um noch genauer zu sein, konstruieren sowohl CG als auch GMRES in der ersten Iteration mit dem Krylov-Raum eine Approximation der Form . CG wählt und GMRES wählt Wenn diagonal mit Einträgen und dann ist der erste CG-Schritt wird doppelt so groß wie der erste GMRES-Schritt. Wahrscheinlich können Sie und konstruieren $K_1 = \{ b \}$ $x_1 = \alpha b$

α = \frac{(b, b)}{(A b, b)}

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

α = \frac{(A b, b)}{(A^{2} b, b)} .

$\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$ so dass dieser Faktor von zwei Unterschieden während der gesamten Iteration anhält, aber ich bezweifle, dass es noch schlimmer wird.

Andrew T. Barker
quelle

2

Sei . Dann , und . Also , aber . Das heißt, der Anfangsvektor hat bereits die richtige Skalierung, um den Rest klein zu machen, muss jedoch mit skaliert werden , um den Fehler klein zu machen.

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}$

Jed Brown

3

Eine Sache ist, dass GMRES niemals dort eingesetzt wird, wo CG angewendet werden kann. Ich glaube nicht, dass es Sinn macht, diese beiden zu vergleichen. Bei SPD-Matrizen ist CG aufgrund der Speicheranforderungen und der oben genannten Gründe definitiv der Gewinner. Eine interessante Frage wäre, eine Erweiterung von CG zu finden, die auf Probleme anwendbar ist, bei denen CG nicht angewendet werden kann. Es gibt Methoden wie BiCG-stab, die nicht wie GMRES eine lineare Speichererhöhung erfordern, aber die Konvergenz ist nicht so gut wie bei GMRES (manchmal sogar bei neu gestartetem GMRES).

user1964178
quelle

2

Es gibt die IDR-Schemata, die die Lücke zwischen GMRES und BiCG in Bezug auf Speichereinsparungen, Stabilität und Konvergenz schließen: ta.twi.tudelft.nl/nw/users/gijzen/IDR.html Ich bin nicht sicher, ob ich GMRES zustimme sollte nicht verwendet werden, wenn CG sein könnte. Wenn Sie eine Cholesky-Faktorisierung einer Matrix durchführen können, die Ihre Energienorm induziert, können Sie diese in eine symmetrische Lanczos-Iteration einspeisen und eine Lösung mit drei Termwiederholungen erhalten, die sich fast wie CG verhält. Natürlich ist CG die einfachere Option, aber die Option ist verfügbar :)

Reid.Atcheson

2

Wenn Sie zum Beispiel einen Krylov-Glatter verwenden, ist GMRES wahrscheinlich vorzuziehen, da es eine schwächere Norm verwendet, die auf größere Eigenwerte abzielt, die tendenziell häufiger sind.

Jed Brown

Probleme, bei denen Conjugate gradient viel besser funktioniert als GMRES

Antworten: