Kann eine Krylov-Subraummethode als Glättungsfaktor für Mehrgitter verwendet werden?

15

Nach meinem Kenntnisstand verwenden Multigrid-Löser iterative Glätter wie Jacobi, Gauss-Seidel und SOR, um den Fehler bei verschiedenen Frequenzen zu dämpfen. Könnte stattdessen eine Krylov-Subraummethode (wie Konjugatgradient, GMRES usw.) verwendet werden? Ich glaube nicht, dass sie als "Glätteisen" klassifiziert sind, aber sie können verwendet werden, um die Grobgitterlösung anzunähern. Können wir eine analoge Konvergenz der Lösung wie bei einer Standardmethode mit mehreren Gittern erwarten? Oder ist es problemabhängig?

Paul
quelle

Antworten:

18

Ja, Sie können, aber Krylov-Methoden haben im Allgemeinen keine guten Glättungseigenschaften. Sie zielen nämlich adaptiv auf das gesamte Spektrum ab, wodurch der Rest oder eine geeignete Norm des Fehlers minimiert wird. Dies schließt im Allgemeinen einige niederfrequente (langwellige) Moden ein, mit denen die groben Gitter gut zurechtgekommen wären. Krylov-Glätter machen den Multigrid-Zyklus auch nichtlinear. Wenn also Multigrid als Vorkonditionierer für eine äußere Krylov-Methode verwendet wird, sollte die äußere Methode "flexibel" sein (z. B. GCR oder FGMRES).

Die Verwendung von Krylov-Glättern erhöht auch die Anzahl der zu berechnenden Skalarprodukte erheblich, was parallel zu einem erheblichen Engpass wird. Trotz dieser unattraktiven Eigenschaften sind Krylov-Glätter manchmal nützlich, insbesondere bei schwierigen Problemen, bei denen keine guten Interpolationsoperatoren verfügbar sind.

λmaxD-1EIND-1EIN(0,1λmax,1.1λmax)15510λmaxλmax

Adams, Brezina, Hu und Tuminaro (2003) sind eine schöne Arbeit über die parallele und algorithmische Leistung von Polynomglättern. Beachten Sie, dass Polynomglätter bei nicht symmetrischen Problemen in der Regel weniger effektiv (und / oder schwierig zu formulieren) sind. In diesem Fall möchten Sie wahrscheinlich Gauß-Seidel oder komplexere (blockierte / verteilte) Relaxationsschemata verwenden.

Jed Brown
quelle
Können Sie eine gute Quelle für Polynom- und / oder Krylov-Smoothers vorschlagen? Ich habe auch noch nie davon gehört :)
Paul
@JedBrown: Meinst du "elliptisch" in der PDE oder bilinearen Form (dh meinst du, dass alle Eigenwerte des Operators oder des Hauptsymbols positiv sind?)? Ich nehme das letztere an, da Sie über Punktblocker Jacobi sprechen.
Jack Poulson
Paul Ich habe eine Referenz hinzugefügt. @Jack Genau genommen sollte der diskrete Operator SPD sein, aber in der Praxis funktionieren die Methoden eher, solange das Spektrum nicht zu schlecht verteilt ist.
Jed Brown