Vorkonditionierung

Die Vorkonditionierung transformiert ein lineares System in ein äquivalentes System mit einem günstigeren Spektrum, sodass ein iterativer Löser in wesentlich weniger Schritten konvergiert; sie ist oft der wichtigste Einzelfaktor für die Leistung großer dünnbesetzter Löser.

Definition

Ein Vorkonditionierer ist eine Matrix, die implizit oder explizit auf ein lineares System angewendet wird und die Koeffizientenmatrix oder ihre Inverse approximiert, sodass das vorkonditionierte System spektrale Eigenschaften aufweist, die zu einer wesentlich schnelleren Konvergenz einer iterativen Methode führen.

Scope

Dieses Thema behandelt die Idee einer approximativen Inversen, die Eigenwerte gruppiert oder die Konditionszahl senkt, die Hauptfamilien von Vorkonditionierern – diagonale und blockdiagonale, unvollständige LU- und Cholesky-Faktorisierungen, dünnbesetzte approximative Inverse sowie Gebietszerlegungs- und Mehrgitter-Vorkonditionierer – und den Kompromiss zwischen der Wirksamkeit eines Vorkonditionierers und seinen Kosten für Aufbau und Anwendung.

Core questions

• Wie verändert ein Vorkonditionierer das Spektrum eines Systems, um die iterative Konvergenz zu beschleunigen?
• Was macht einen guten Vorkonditionierer aus, der die Approximationsqualität mit den Konstruktions- und Anwendungskosten in Einklang bringt?
• Wie werden unvollständige Faktorisierungen und dünnbesetzte approximative Inverse konstruiert?
• Wann werden Mehrgitter- oder Gebietszerlegungsmethoden als Vorkonditionierer und nicht als eigenständige Löser verwendet?

Key theories

Spektrale Transformation

Die Anwendung eines Vorkonditionierers, der die Inverse der Matrix approximiert, führt zu einem vorkonditionierten Operator, dessen Eigenwerte gruppiert sind oder dessen Konditionszahl reduziert ist; da die Krylov-Konvergenz vom Spektrum abhängt, kann dies die Iterationszahl um Größenordnungen verringern.

Vorkonditionierer mit unvollständiger Faktorisierung

Unvollständige LU- und unvollständige Cholesky-Faktorisierungen berechnen approximative Dreiecksfaktoren, während Füll-in-Elemente jenseits eines gewählten Sparsity-Musters oder Schwellenwerts verworfen werden, wodurch ein kostengünstiger Vorkonditionierer entsteht, der einen Großteil der Matrixwirkung erfasst.

Mechanisms

Ein Vorkonditionierer M wird so gewählt, dass die Lösung von Systemen mit M kostengünstig ist und der vorkonditionierte Operator nahe an der Identität liegt, wodurch seine Eigenwerte gruppiert werden. Die diagonale (Jacobi-)Vorkonditionierung skaliert einfach neu; unvollständige LU- oder Cholesky-Faktorisierungen erstellen approximative dünnbesetzte Dreiecksfaktoren, indem kleine oder außerhalb des Musters liegende Einträge während der Elimination weggelassen werden; dünnbesetzte approximative Inverse konstruieren direkt ein dünnbesetztes M, das die Inverse approximiert, sodass nur Matrix-Vektor-Produkte benötigt werden. Leistungsfähigere Vorkonditionierer wenden pro Iteration einen Mehrgitterzyklus oder eine Gebietszerlegungslösung an. In jedem Fall wird der Vorkonditionierer innerhalb jedes Schritts einer Krylov-Methode angewendet, und sein Design gleicht ab, wie gut er die Inverse approximiert, und wie viel seine Erstellung und Anwendung kostet.

Clinical relevance

Die Vorkonditionierung ist entscheidend für die Lösung der enormen schlecht konditionierten Systeme aus PDE-Diskretisierungen und großskaliger Optimierung; der richtige Vorkonditionierer kann eine Iteration, die stagniert, in eine umwandeln, die in wenigen Schritten konvergiert, und die Auswahl und Abstimmung von Vorkonditionierern ist ein zentrales praktisches Anliegen in der rechnergestützten Wissenschaft und Ingenieursoftware.

History

Die Vorkonditionierung entwickelte sich ab den 1970er Jahren parallel zu den Krylov-Methoden, wobei unvollständige Faktorisierungen 1977 von Meijerink und van der Vorst eingeführt wurden und seitdem eine breite Palette algebraischer und mehrstufiger Vorkonditionierer entwickelt wurde; sie wird heute oft als wichtiger für die Löserleistung angesehen als die Wahl der Krylov-Methode selbst.

Key figures

• Yousef Saad
• Michele Benzi
• Henk van der Vorst
• Olof Widlund

Seminal works

• saad2003
• benzi2002

Frequently asked questions

Was macht einen Vorkonditionierer gut?

Ein guter Vorkonditionierer approximiert die Inverse der Matrix eng, sodass das vorkonditionierte System für die iterative Methode einfach zu lösen ist, und ist dennoch kostengünstig in Konstruktion und Anwendung. Die Kunst besteht darin, diese konkurrierenden Ziele auszubalancieren: Ein genauerer Vorkonditionierer kostet pro Schritt mehr, benötigt aber weniger Schritte.

Kann ein Löser als Vorkonditionierer verwendet werden?

Ja. Ein einzelner Mehrgitterzyklus oder eine Gebietszerlegungslösung wird häufig als Vorkonditionierer innerhalb einer Krylov-Methode verwendet, wodurch die Robustheit der Krylov-Iteration mit der schnellen Fehlerreduktion des inneren Lösers kombiniert wird.