Welche Richtlinien sollten bei der Suche nach guten Vorkonditionierungsmethoden für ein bestimmtes Problem verwendet werden?

Für die Lösung großer linearer Systeme mit iterativen Methoden ist es häufig von Interesse, Vorkonditionierung einzuführen, zB anstelle von M - 1 aufzulösen ( A x = b ) , wobei M hier für die linke Vorkonditionierung des Systems verwendet wird. Normalerweise sollten wir haben M - 1 ≈ A - 1 und bilden die Grundlage für (viel mehr) effiziente Lösung oder Reduzierung der Rechenressourcen (zB Speicher) im Vergleich mit der Lösung des ursprünglichen Systems (dh wenn M = $Ax=b$$M^{-1}(Ax=b)$$M$$M^{-1}\approx A^{-1}$$M=A$). Welche Richtlinien sollten wir jedoch verwenden, um den Vorkonditionierer auszuwählen? Wie machen Praktiker das für ihr spezifisches Problem?

Ich wollte ursprünglich keine Antwort geben, weil dies eine sehr lange Behandlung verdient, und hoffentlich wird es noch jemand anderes geben. Ich kann jedoch mit Sicherheit einen sehr kurzen Überblick über den empfohlenen Ansatz geben:

1. Führen Sie eine gründliche Literaturrecherche durch.
2. Wenn dies fehlschlägt, versuchen Sie es mit jedem Vorkonditionierer, den Sie in die Finger bekommen können. MATLAB, PETSc und Trilinos sind dafür gute Umgebungen.
3. Wenn dies fehlschlägt, sollten Sie sorgfältig über die Physik Ihres Problems nachdenken und prüfen, ob es möglich ist, eine kostengünstige Näherungslösung zu finden, möglicherweise sogar für eine geringfügig geänderte Version Ihres Problems.

Beispiele für 3 sind verschobene Laplace-Versionen von Helmholtz und die jüngsten Arbeiten von Jinchao Xu zur Vorkonditionierung des biharmonischen Operators mit Laplace-Operatoren.

Andere haben bereits die Frage der Vorkonditionierung von sogenannten "monolithischen" Matrizen kommentiert, z. B. die diskretisierte Form einer Skalargleichung wie der Laplace-Gleichung, der Helmholtz-Gleichung oder, wenn Sie sie verallgemeinern wollen, der Vektorwert Elastizitätsgleichung. Für diese Dinge ist es klar, dass Multigrid (entweder algebraisch oder geometrisch) der Gewinner ist, wenn die Gleichung elliptisch ist, und für andere Gleichungen ist es nicht ganz so klar - aber so etwas wie SSOR funktioniert oft ziemlich gut (für irgendeine Bedeutung von "angemessen").

Für mich war die große Offenbarung, was bei nicht monolithischen Problemen zu tun ist, zum Beispiel für den Stokes-Operator Als ich vor ungefähr 15 Jahren mit der numerischen Analyse begann, hoffte man, dass die gleichen Techniken auf solche Matrizen wie oben angewendet werden könnten, und die Forschungsrichtung bestand darin, entweder direkt Multigrid zu versuchen oder Verallgemeinerungen von SSOR zu verwenden (unter Verwendung von " point smoothers "wie Vanka) und ähnliche Methoden. Aber das ist verblasst, da es nicht sehr gut funktioniert.

$$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$$

Was dies ersetzt hat, war das, was anfänglich als "physikalisch-basierte Vorkonditionierer" und später einfach (und vielleicht genauer) als "Block-Vorkonditionierer" von Silvester und Wathen bezeichnet wurde. Diese basieren oft auf Blockeliminierungen oder Schur-Ergänzungen und die Idee ist, einen Vorkonditionierer so aufzubauen, dass man Vorkonditionierer für einzelne Blöcke wiederverwenden kann, von denen bekannt ist, dass sie gut funktionieren. Im Fall der Stokes-Gleichung verwendet beispielsweise der Silvester / Wathen-Vorkonditionierer die Matrix

$$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-1}$$ bei Verwendung als Vorkonditionierer mit GMRES würde dies zu einer Konvergenz in genau zwei Iterationen führen. Da es dreieckig ist, ist die Inversion auch viel einfacher, aber wir haben immer noch das Problem, was wir mit den diagonalen Blöcken machen sollen, und dort verwendet man Näherungen: wobei die Tilde bedeutet, die genaue Inverse durch eine Näherung zu ersetzen. Dies ist oft viel einfacher: weil der A- Block ein elliptischer Operator ist, ~ A - $$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$$ $A$$\widetilde{A^{-1}}$wird auch durch ein Mehrgitter V-Zyklus, beispielsweise angenähert, und es stellt sich heraus , daß hier, ist gut durch einen ILU einer Masse Matrix approximiert.$\widetilde{(B^T A^{-1} B)^{-1}}$

Diese Idee, mit den einzelnen Blöcken, aus denen die Matrix besteht, zu arbeiten und Vorkonditionierer wiederzuverwenden, hat sich als enorm leistungsfähig erwiesen und unsere heutigen Vorstellungen zur Vorkonditionierung von Gleichungssystemen grundlegend verändert. Dies ist natürlich relevant, da es sich bei den meisten tatsächlichen Problemen tatsächlich um Gleichungssysteme handelt.

Jack hat ein gutes Verfahren angegeben, um einen Vorkonditionierer zu finden. Ich werde versuchen eine Adresse mit der Frage "Was macht einen guten Vorkonditionierer aus?" Die operative Definition lautet:

$A x = b$$M^{-1}$$A^{-1}$

Dies gibt uns jedoch keinen Einblick in die Konstruktion eines Vorkonditionierers. Die meisten Vorkonditionierer basieren auf der Manipulation des Operator-Spektrums. Im Allgemeinen konvergieren Krylov-Methoden schneller, wenn Eigenwerte in Gruppen zusammengefasst werden (siehe Matrixiterationen oder meromorphe Funktionen und lineare Algebra) . Manchmal können wir nachweisen, dass ein Vorkonditionierer nur aus wenigen eindeutigen Eigenwerten besteht, z. B. Ein Hinweis zur Vorkonditionierung für unbestimmte lineare Systeme .

Ein Beispiel für eine gemeinsame Strategie ist Multigrid. Entspannungskonditionierer (hier Smoothers) wie SOR entfernen im Fehler hochfrequente Anteile. Wenn das Residuum auf ein grobes Gitter projiziert wird, werden niederfrequente Fehlerkomponenten höher und können erneut von SOR angegriffen werden. Diese grundlegende Strategie liegt komplizierteren MG-Versionen wie AMG zugrunde. Beachten Sie, dass der Solver die niedrigsten Fehlerfrequenzen genau auflösen muss.

Eine andere Strategie besteht darin, die Gleichung in kleinen Teilräumen zu lösen. Genau das tun Krylov-Löser. In der einfachsten Form ist dies die Kaczmarz-Methode oder die Additiv-Schwarz-Methode . Die fortgeschrittene Theorie, Domain Decomposition , konzentriert sich auf die spektrale Approximation des Fehlers an der Grenzfläche, da angenommen wird, dass die Domänen ziemlich genau gelöst sind.

Dann gibt es eine Reihe von Dingen, die Betreiber in der Nähe produzieren $A$