Ist es üblich, in Multigrid keine Konvergenzprüfung durchzuführen?

12

Ich habe gerade Kapitel 3 in "A Multigrid Tutorial" von Briggs / Henson / McCormick gelesen, Link .

Der Text handelt von Multigrid-Zyklen wie V-Zyklus, Mu-Zyklus, FMG. Was mir aufgefallen ist: Bei den meisten iterativen Verfahren wird geprüft, ob die gewünschte Toleranz / Genauigkeit erreicht wurde, und wenn dies der Fall ist, wird das Verfahren abgebrochen. Briggs / Henson / McCormick verwenden in den vorgestellten Schemata jedoch keine Konvergenzprüfung. Die Anzahl der Iterationen und Rekursionen ist nur fest codiert und man muss darauf vertrauen, dass das Schema konvergiert.

Wie wird das normalerweise in Multigrid gemacht? Ist es üblich, dass die Anzahl der Iterationen / Rekursionen nur fest codiert ist? Ich befürchte wirklich, dass ich entweder viel Rechenzeit verschwenden werde, weil ich zu genau bin, oder andererseits die Genauigkeit in vielen Fällen schlecht ist, wenn ich eine geringere Anzahl von Iterationen / Rekursionen wähle.

Michael
quelle
Das Fehlen von Antworten auf diese Frage ist für mich wirklich überraschend. Sicherlich gibt es hier einige sehr aktive Benutzer, die über umfangreiche Erfahrung in der Forschung und / oder Produktion verfügen.
Doug Lipinski
2
Ich denke, das Problem ist, dass Multigrid heutzutage selten als eigenständiger Löser verwendet wird (aufgrund der fehlenden allgemeinen Konvergenztheorie, glaube ich), sondern als Vorbedingung für eine etabliertere iterative Methode wie CG oder GMRES. In diesem Zusammenhang ist keine Konvergenzprüfung für Multigrid erforderlich, da sich die äußere Iteration darum kümmert.
Christian Clason

Antworten:

4

Ja, es ist aus verschiedenen Gründen normal, dass in MG keine Konvergenzprüfungen durchgeführt werden. Erstens ist der MG-Operator nicht mehr linear, wenn Sie bei jedem Durchlauf eine andere Anzahl von Iterationen verwenden, und Sie müssten so etwas wie FGMRES als Beschleuniger verwenden, der einen nichtlinearen Vorkonditionierer aufnehmen kann. Zweitens ist FMG ein exakter Löser (reduziert den Fehler unter den Diskretisierungsfehler), wenn er funktioniert. Die Überprüfung der Konvergenz führt zu einer kostspieligen Synchronisierung des Algorithmus. Sie würden im Allgemeinen am Ende nur überprüfen, um die Konvergenz zu überprüfen.

Matt Knepley
quelle
Haben Sie Quellen, um dies zu sichern? Derzeit widersprechen sich Ihre Antwort und die der anderen am besten bewerteten Antworten direkt.
Doug Lipinski
1) Saads Buch ist die beste Referenz für die Verwendung von FGMRES, um einen sich ändernden Vorkonditionierer aufzunehmen: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) Ich glaube, der Beweis, dass FMG den Fehler unter den Diskretisierungsfehler reduziert, ist ausreichend leistungsfähig V-Cycle ist in Trottenberg und Osterlee, aber ich reproduziere den Beweis in meinem Buch: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf
Matt Knepley
4

Definitiv nicht. Das Buch Multigrid enthält ein Diagramm auf Seite 53 (Abbildung 2.10), in dem die Abnahme des Residuums als Funktion der Anzahl der V- oder W-Zyklen dargestellt ist. Sie würden mit dem Radfahren aufhören, wenn Sie mit der Größe des Rests zufrieden sind.

Die Ursache Ihrer Verwirrung kann sein, dass einige Beschreibungen nur einen einzelnen V-Zyklus beschreiben. In einigen wenigen Fällen kann dies zu einer geeigneten Lösung führen, da Multigrid eine so leistungsstarke Technik ist. Multigrid kann auch als Vorkonditionierer verwendet werden . In diesem Fall ist das Multigrid nur ein Beschleuniger, und die Konvergenzprüfung erfolgt auf einer höheren Ebene. Die Überprüfung sollte jedoch immer irgendwo stattfinden.

Damaststahl
quelle
1
Haben Sie Quellen, um dies zu sichern? Derzeit widersprechen sich Ihre Antwort und die der anderen am besten bewerteten Antworten direkt.
Doug Lipinski
1

Bei Multigrid als Löser wird normalerweise die relative Norm des Residuums als Stoppkriterium verwendet . Wenn Sie dieses Verhältnis verringern, sollte sich die Genauigkeit der Lösung erhöhen. Außerdem machen Forscher auf der gröbsten Ebene verschiedene Dinge:

  1. entweder mit einem direkten Löser lösen (keine Konvergenz)
  2. Verwenden Sie feste Iterationen (keine Konvergenz)
  3. Verwenden Sie den sukzessiven Unterschied zwischen den Iterationen als Konvergenzkriterium (keine gute Methode, da Sie möglicherweise weit von der Lösung entfernt sind).
  4. Verwenden Sie wieder die relative Norm des Rests als Stoppkriterium.

Die oben aufgeführte Methode 2 auf der gröbsten Ebene ist gut, wenn Multigrid als Vorkonditionierer verwendet wird (Multigrid-Experten können dies hier kommentieren - ich bin ein Anfänger).

Also, im allgemeinen Konvergenz gebraucht .

Gaurav Saxena
quelle