Taxonomie von ILU-Vorkonditionierern

8

Ich habe gelernt, dass es für den BiCGStab-Solver für spärliche lineare Systeme so gut wie immer erforderlich ist, einen Vorkonditionierer zu verwenden. Inzwischen wurde mir klar, dass die Auswahl eines guten problemabhängig ist.

Beim Surfen im Internet habe ich herausgefunden, dass es viele ILU-basierte Vorkonditionierer gibt (ILUT, MILU usw.). Hier war ich verwirrt.

Ich habe mich gefragt, ob jemand die Taxonomie von ILU-Vorkonditionierern kurz erklären, einige Literaturquellen für bestimmte angeben kann und welche davon für BiCGStab geeignet sind.

Die Einstellung, in der ich arbeite, ist CFD, und Code basiert auf einer unstrukturierten Diskretisierung endlicher Volumina. Wahrscheinlich werden unterschiedliche Vorkonditionierer für Impulsgleichungen und Transportgleichungen für Turbulenzskalare benötigt.

John Travolta
quelle

Antworten:

9

Ein Vorkonditionierer, beispielsweise M, ist eine Annäherung an die Systemmatrix, beispielsweise A, die das Problem in ein anderes Problem mit verbessertem Eigenwertspektrum umwandelt. Ein perfekter Vorkonditionierer wäre invers zu A, dh inv (M) = A.

Leider ist diese Umkehrung normalerweise nicht verfügbar, zu kompliziert zu berechnen, benötigt mehr Speicherplatz aufgrund der während der Faktorisierung eingeführten Füllungen und kann auch unter Rundungsfehlern leiden. Daher sollte ein Vorkonditionierer leicht zu berechnen und anzuwenden sein und dennoch effektiv.

Neben den grundlegenden Vorkonditionierern wie Jacobi oder Gauss-Seidel (oder SOR) ist ILU (IC bei symmetrischen Problemen - Sie arbeiten an CFD, also die Systeme oder nicht symmetrisch) einer der häufigsten Vorkonditionierer.

Die Auswahl des Vorkonditionierers hängt normalerweise von Ihrem Problem ab. ILU hat viele Varianten wie ILUT, ILUS, MILU usw. Sie können die Literatur konsultieren, die ich am Ende hinzugefügt habe. Bei Problemen mit leichten Schwierigkeiten kann ILU (0) verwendet werden. Wenn die Probleme jedoch schwieriger werden, dh die Reynolds-Zahl steigt, sollten mehr Füllungen (z. B. ILU (1)) mit Schwellenwertstrategien (ILUT) verwendet werden. Das Problem ist, dass fortgeschrittene Verwendungen von ILU mehr Speicher und die Bestimmung des Sparsity-Musters erfordern, das sich jetzt von Ihrer Systemmatrix unterscheidet. In diesem Fall müssen Sie das Spartisitätsmuster zuerst symbolisch und später numerisch berechnen.

Es gibt verschiedene Ideen, um den Rechenaufwand zu reduzieren.

  • Verwendung von verzögerten Vorkonditionierern, bei denen Sie eine Neuberechnung des Vorkonditionierers vermeiden, selbst wenn das lineare System variiert.
  • Verwendung eines LU-SGS-ähnlichen Vorkonditionierers, der mit Flussaufteilungsalgorithmen effizient implementiert werden kann.
  • Verwendung von matrixfreien Methoden - die ich in meiner Doktorarbeit bevorzugt habe. Newton-Krylov-Löser, bei denen der Jacobi nicht benötigt wird, erwarten einen Vorkonditionierer, der normalerweise mit einer Näherung niedriger Ordnung und wahrscheinlich mit farbbasierten Algorithmen berechnet wird (allerdings schwieriger bei unstrukturierten Problemen).
  • Verwendung nur von Diffusionsoperatoren wie Laplace und Vermeidung konvektiver Begriffe (nicht effizient bei der Reduzierung der Anzahl von Iterationen)
  • Multigrid, bei dem Sie einen einfachen Smoother wie w-Jacobi oder SOR in einer Rasterhierarchie verwenden. Für unstrukturierte Probleme sollten Sie Algebraic Multigrid (AMG) anstelle von geometrischen verwenden.
  • und viele andere (multipliziere die Anzahl meiner Einträge mit 10) ..

Da das Problem nicht symmetrisch ist, müssen hauptsächlich zwei Löser verwendet werden: GMRES oder BiCGStab. (QMR oder TFQMR sind eine andere Alternative, aber ich glaube, dass die Leistung unter diesen beiden liegt). GMRES ist normalerweise ein besserer Löser, wenn Sie noch kein Speicherproblem haben. Aufgrund der gespeicherten Vektoren ist ein Neustart erforderlich. Dies ist ein Problem, wenn der Vorkonditionierer schlecht ist oder Sie einen sehr großen dof haben. BiCGStab benötigt nur vier Matrix-Vector-Produkte, was für große Probleme geeignet ist, aber normalerweise GMRES unterlegen ist. (Ich habe GMRES bevorzugt, aber ich mag BiCGStab sehr!)

All dieses Problem mit dem Vorkonditionierer und dem linearen Löser ist sehr komplex. Ich kann einige Bücher zum Lesen vorschlagen. Ihr Ausgangspunkt sollten Vorlagen für die Lösung linearer Systeme sein. Dies ist ein kostenloses Buch. Smoothers sowohl als eigenständige Löser als auch als Vorkonditionierer für Krylov-Löser werden in diesem Buch erläutert. Sie können sich auch an Yousef Saads "Iterative Methoden für spärliche lineare Systeme" wenden. Es ist endgültig in der Bibliothek Ihrer Institution. Erste Ausgabe ist auch verfügbar hier .

Bevor Sie zum Schluss kommen, empfehle ich Ihnen, sich Frameworks wie Petsc , Trilinos oder sogar Hypre sowie die von 1 bereitgestellten Dateien anzusehen . Sie bieten Vorkonditionierer mit etwas Programmierung. Es gibt tatsächlich mehr Bücher zu bieten, aber werfen Sie auch einen Blick auf Ke Chens "Matrix Preconditioning Techniques and Applications". Matlab-Codes sind im Buch verfügbar.

Viel Glück auf Ihrer Reise, Sie werden es brauchen.

Erhururan
quelle
Vielen Dank! Ich habe beide Bücher und grabe immer noch - das ist wirklich ein interessantes Thema!
Johntra Volta
2

Das Buch von Y. Saad ist auch eine der Standardreferenzen für Löser und Vorkonditionierer.

Wolfgang Bangerth
quelle
Ich verstehe inzwischen, dass er einer der Helden der Krylov-Raumfahrtmethoden ist. Ich würde ihn wahrscheinlich mit Fragen zu Tode langweilen, wenn er mein Berater wäre.
Johntra Volta