Richtlinien für verschachtelte Vorkonditionierer

Stellen Sie sich die Situation vor, in der Sie ein lineares System mit einer vorkonditionierten Krylov-Methode lösen möchten. Um den Vorkonditionierer selbst anzuwenden, müssen Sie jedoch ein Hilfssystem lösen, das mit einer anderen vorkonditionierten Krylov-Methode durchgeführt wird.

In einem Extremfall können Sie die innere Lösung innerhalb jedes Schritts der äußeren Lösung zur Konvergenz ausführen.
Auf der anderen Seite könnten Sie die innere Lösung überhaupt nicht durchführen, sondern sie durch die innere Vorkonditionierung ersetzen.
Irgendwo in der Mitte können Sie die innere Krylov-Schleife nach einer festgelegten Anzahl von Iterationen oder nach Erreichen einer bestimmten Toleranz abschneiden.

Empirisch bin ich auf Situationen gestoßen, in denen das erste Extrem besser ist, und auf verschiedene Situationen, in denen das zweite Extrem besser ist (in Bezug auf die Gesamtkosten). Ich kann jedoch keinen klaren Grund finden, warum bestimmte Situationen eine Strategie einer anderen vorziehen.

Gibt es eine Anleitung oder Theorie darüber, wann diese unterschiedlichen Strategien vorzuziehen sind?

preconditioning krylov-method Nick Alger
quelle

Für mindestens die dritte (Zwischen-) Situation in Ihrer Liste könnten Simoncini und Szyld, Flexible Inner-Outer Krylov Subspace Methods, SIAM J. Numer, ein guter Ausgangspunkt sein. Anal. 40, S. 2219-2239.

Andrew T. Barker

Vielen Dank für den Hinweis, ich bin gespannt, was sie dort haben. Seltsamerweise habe ich in der Praxis festgestellt, dass verschiedene Formen der Zwischensituation die mit Abstand schlechteste Leistung erbringen. Wenn die Toleranz- / Iterationsnummer festgelegt ist, neigt der äußere Löser dazu, auf der Fehlerstufe der inneren Toleranz zu hängen. Es scheint auch schlechter zu sein, mit einer großen inneren Toleranz zu beginnen und sie mit fortschreitender äußerer Methode zu verringern, als zunächst nur die innere Toleranz klein einzustellen.

Nick Alger

Verwenden Sie flexible Krylov-Methoden? Die Ergebnisse, die Sie beschreiben, sind das, was ich erwarten würde, wenn Sie es nicht wären. Die Zwischensituation ist genau die, in der sich der Vorkonditionierer bei jeder Iteration (geringfügig) unterscheidet, wenn flexible Krylov-Methoden erforderlich sind.

Andrew T. Barker

Antworten:

Diese Frage ist schon lange offen, aber ich denke, sie verdient es immer noch, beantwortet zu werden.

$\tilde x = K(A,P,\tau,N; b)$ $K$ $Ax=b$ $N$ $\tau$ $P\approx A^{-1}$ $K$ $b$

$K(A,P,0,\infty;\cdot)$ $Ax=b$ $K(A,P,0,\infty;b)=A^{-1}b$ $b$ $b$ $r^{(0)}=b-Ax^{(0)}$ $K(A,P,\tau,N; \cdot)$ $N$ $\tau$

$K(A,P,\tau,N; \cdot)$ $A$

Dies steht im Gegensatz zu vielen anderen Methoden, die zur Vorkonditionierung verwendet werden: Beispielsweise ist ein SSOR-Schritt eine lineare Operation auf den Vektor, auf den Sie ihn anwenden, ebenso wie alle anderen Methoden, die einen Schritt einer Festpunktiteration anwenden.

Das grundlegende Problem besteht nun darin, dass die meisten Krylov-Raumfahrtverfahren erfordern, dass der Vorkonditionierer ein linearer Operator ist. Sie konvergieren einfach nicht, wenn der Vorkonditionierer nicht linear ist, was Ihre Beobachtung erklärt. Auf der anderen Seite gibt es Variationen einiger Krylov-Raumfahrtmethoden - typischerweise mit dem Wort "Flexibel" vorangestellt, wie F-GMRES in "Flexible GMRES" -, die dies umgehen und mit Vorkonditionierern umgehen können, die nicht linear sind Betreiber. Diese flexiblen Varianten der ursprünglichen Methoden konvergieren immer noch und sind häufig leistungsstarke Methoden, wenn sie mit guten (aber nichtlinearen) Vorkonditionierern gekoppelt werden.

Wolfgang Bangerth
quelle