Warum konvergiert mein iterativer linearer Löser nicht?

Was kann schief gehen, wenn mit vorkonditionierten Krylov-Methoden von KSP ( dem linearen Lösungspaket von PETSc ) ein spärliches lineares System gelöst wird, wie es durch Diskretisierung und Linearisierung partieller Differentialgleichungen erhalten wird?

Welche Schritte kann ich unternehmen, um festzustellen, was bei meinem Problem schief läuft?

Welche Änderungen kann ich vornehmen, um mein lineares System erfolgreich und effizient zu lösen?

Erstberatung

• Laufen Sie immer mit, -ksp_converged_reason -ksp_monitor_true_residualwenn Sie herausfinden möchten, warum eine Methode nicht konvergiert.
• Machen Sie die Problemgröße und die Anzahl der Prozesse so klein wie möglich, um den Fehler zu demonstrieren. Sie gewinnen häufig Einsicht, indem Sie feststellen, welche kleinen Probleme das Verhalten hervorrufen, das zum Ausfall Ihrer Methode führt und die Bearbeitungszeit verkürzt. Darüber hinaus gibt es einige Untersuchungstechniken, die nur für kleine Systeme verwendet werden können.
• Wenn das Problem erst nach einer großen Anzahl von Zeitschritten, Fortsetzungsschritten oder nichtlinearen Lösungsschritten auftritt, sollten Sie den Modellstatus beim Auftreten eines Fehlers aufschreiben, damit Sie schnell experimentieren können.
• Alternativ, insbesondere wenn Ihre Software keine Checkpoint-Fähigkeit besitzt, können Sie das lineare System mit -ksp_view_binaryoder MatView()speichern. Verwenden Sie dann den Code unter $PETSC_DIR/src/ksp/ksp/examples/tutorials/ex10.c, um die Matrix einzulesen und zu lösen (möglicherweise mit einer anderen Anzahl von Prozessen). Dies erfordert eine zusammengesetzte Matrix, so dass ihre Nützlichkeit etwas eingeschränkt sein kann.
• Es gibt viele mögliche Löseroptionen (z. B. eine unendliche Anzahl, die in der Befehlszeile von PETSc aufgrund einer beliebigen Anzahl von Kompositionsebenen verfügbar ist). In dieser Frage finden Sie allgemeine Ratschläge zur Auswahl linearer Löser.

Häufige Gründe dafür, dass KSP nicht konvergiert

• Die Gleichungen sind zufällig singulär (zB vergessen, Randbedingungen aufzuerlegen). Überprüfen Sie dies für ein kleines Problem mit -pc_type svd -pc_svd_monitor. Versuchen Sie auch einen direkten Löser mit -pc_type lu(z -pc_type lu -pc_factor_mat_solver_package superlu_dist. B. über ein Drittanbieterpaket ).
• Die Gleichungen sind absichtlich singulär (z. B. konstanter Nullraum), aber die Krylov-Methode wurde nicht informiert, siehe KSPSetNullSpace().
• Die Gleichungen sind absichtlich singulär und KSPSetNullSpace()wurden verwendet, aber die rechte Seite ist nicht konsistent. Sie müssen möglicherweise MatNullSpaceRemove()auf der rechten Seite anrufen, bevor Sie anrufen können KSPSolve().
• Die Gleichungen sind unbestimmt, so dass Standardkonditionierer nicht funktionieren. Normalerweise kennen Sie dies aus der Physik, aber Sie können dies mit -ksp_compute_eigenvalues ​​überprüfen -ksp_gmres_restart 1000 -pc_type none. Versuchen Sie es bei einfachen Sattelpunktproblemen -pc_type fieldsplit -pc_fieldsplit_type schur -pc_fieldsplit_detect_saddle_point. Weitere Informationen finden Sie im Benutzerhandbuch und auf der PCFIELDSPLIT-Manpage . Lesen Sie bei schwierigeren Problemen die Literatur, um zuverlässige Methoden zu finden, und fragen Sie hier (oder [email protected]oder [email protected]), ob Sie Tipps zur Implementierung dieser Methoden benötigen . Sehen Sie sich diese Frage zum Beispiel für hochfrequentes Helmholtz an. Sehen Sie bei bescheidenen Problemgrößen nach, ob Sie nur mit einem direkten Löser leben können.
• Wenn die Methode in vorkonditioniertem Residuum konvergiert, aber nicht in echtem Residuum, ist der Vorkonditionierer wahrscheinlich singulär oder nahezu singulär. Dies ist häufig bei Sattelpunktproblemen (z. B. inkompressiblem Fluss) oder stark unsymmetrischen Operatoren (z. B. hyperbolischen Low-Mach-Problemen mit großen Zeitschritten) der Fall.
• Der Vorkonditionierer ist zu schwach oder instabil. Prüfen Sie, ob sich -pc_type asm -sub_pc_type ludie Konvergenzrate verbessert. Wenn GMRES beim Neustart zu viel Fortschritt verliert, prüfen Sie, ob ein längerer Neustart hilft -ksp_gmres_restart 300. Wenn eine Transponierte verfügbar ist, versuchen Sie -ksp_type bcgsoder andere Methoden, die keinen Neustart erfordern. (Beachten Sie, dass die Konvergenz mit diesen Methoden häufig fehlerhaft ist.)
• Die Vorkonditionierungsmatrix befindet sich möglicherweise nicht in der Nähe des (möglicherweise nicht zusammengebauten) Bedieners. Versuchen Sie es mit einem direkten Löser, entweder seriell mit -pc_type luoder parallel mit einem Paket eines Drittanbieters (z . B. -pc_type lu -pc_factor_mat_solver_package superlu_distoder mumps). Die Methode sollte in einer Iteration konvergieren, wenn die Matrizen identisch sind, und ansonsten in einer "kleinen" Anzahl von Iterationen. Versuchen Sie -snes_type test, die Matrizen zu überprüfen, wenn Sie ein nichtlineares Problem lösen.
• Der Vorkonditionierer ist nichtlinear (z. B. eine verschachtelte iterative Lösung), versuchen Sie es -ksp_type fgmres or -ksp_type gcr.
• Sie verwenden ein geometrisches Mehrgitter, aber einige Gleichungen (häufig Randbedingungen) sind nicht kompatibel zwischen Ebenen skaliert. Versuchen Sie -pc_mg_galerkin, einen korrekt skalierten Groboperator algebraisch zu konstruieren, oder stellen Sie sicher, dass alle Gleichungen auf die gleiche Weise skaliert sind, wenn Sie rediskretisierte Grobstufen verwenden möchten.
• Die Matrix ist sehr schlecht konditioniert. Überprüfen Sie die Konditionsnummer mit den hier beschriebenen Methoden . Versuchen Sie es zu verbessern, indem Sie die relative Skalierung der Komponenten / Randbedingungen wählen. Versuchen Sie es -ksp_diagonal_scale -ksp_diagonal_scale_fix. Ändern Sie möglicherweise die Formulierung des Problems, um freundlichere algebraische Gleichungen zu erhalten. Wenn Sie die Skalierung nicht korrigieren können, müssen Sie möglicherweise einen direkten Löser verwenden.
• Die Matrix ist nichtlinear (z. B. durch finite Differenzierung einer nichtlinearen Funktion bewertet). Probieren Sie verschiedene Differenzierungsparameter aus (z -mat_mffd_type ds. B. ). Versuchen Sie es mit höherer Präzision, um die Differenzierung genauer zu machen ./configure --with-precision=__float128 --download-f2cblaslapack. Überprüfen Sie, ob es in "einfacheren" Parameterregimen konvergiert.
• Eine symmetrische Methode wird für ein nicht symmetrisches Problem verwendet.
• Klassische Gram-Schmidt wird instabil, versuchen -ksp_gmres_modifiedgramschmidtoder verwenden Sie eine Methode, die anders orthogonalisiert, z -ksp_type gcr.

Mein Rat an die Schüler ist, in diesen Fällen einen direkten Löser zu versuchen. Der Grund ist, dass es zwei Klassen von Gründen gibt, warum ein Löser möglicherweise nicht konvergiert: (i) die Matrix ist falsch, oder (ii) es liegt ein Problem mit dem Löser / Vorkonditionierer vor. Direktlöser liefern fast immer etwas, das Sie mit der erwarteten Lösung vergleichen können. Wenn die Antwort des Direktlösers also richtig aussieht, wissen Sie, dass das Problem mit dem iterativen Löser / der iterativen Vorbedingung zusammenhängt. Wenn die Antwort jedoch falsch aussieht, besteht das Problem darin, die Matrix und die rechte Seite zusammenzusetzen.

Ich verwende normalerweise nur UMFPACK als direkten Löser. Ich bin mir sicher, dass es einfach ist, mit PETSC etwas Ähnliches zu versuchen.