FAS-Multigrid langsamer als lineare Defektkorrektur?

9

Ich habe einen V-Cycle-Multigrid-Solver implementiert, der sowohl eine lineare Fehlerkorrektur (LDC) als auch ein vollständiges Approximationsschema (FAS) verwendet.

Mein Problem ist folgendes: Bei Verwendung von LDC wird der Rest um einen Faktor von ~ 0,03 pro Zyklus reduziert. Die FAS-Implementierung konvergiert zwar auch mit einem linearen Faktor, der Faktor beträgt jedoch nur ~ 0,58. Somit benötigt FAS etwa die 20-fache Anzahl von Zyklen.

Der größte Teil des Codes wird gemeinsam genutzt. Der einzige Unterschied besteht in den von LDC verwendeten Down / Up-Berechnungen

unten: uH:=0,bH:=IhH(bhLhuh)

up: uh:=uh+IHhuH

und FAS verwendet

unten: uH:=IhHuh,bH:=IhHbh+LHIhHuhIhHLhuh

up: uh:=uh+IHh(uHIhHuh)

Meine Testeinstellung stammt aus Briggs "A Multigrid Tutorial, Second Edition", S. 22. 64, hat die analytische Lösung

u(x,y)=(x2x4)(y4y2)mit x,y[0,1]2

Lv=Δu=:bLv=0

u(x,y)=0v=1

Da sich nur der Down / Up-Code unterscheidet, die LDC-Ergebnisse dem Buch entsprechen und das FAS zumindest auch zu funktionieren scheint, habe ich keine Ahnung, warum es in derselben linearen Einstellung so viel langsamer ist.

=01015101

Da ein Bild mehr sagt als Worte:

// first cycle, levels 0-4
// DOWN
VCycle top 4, start               res_norm 3.676520e+02 // initial residual
VCycle top 4, cycle 0, current 4, res_norm 3.676520e+02
VCycle top 4, cycle 0, current 4, res_norm 1.520312e+02 // relaxed (2 iterations)
VCycle tau_norm 2.148001e+01 (DEBUG calculation)
VCycle top 4, cycle 0, current 3, res_norm 1.049619e+02 // restricted
VCycle top 4, cycle 0, current 3, res_norm 5.050392e+01 // relaxed (2 iterations)
VCycle top 4, cycle 0, current 2, res_norm 3.518764e+01 // restricted
VCycle top 4, cycle 0, current 2, res_norm 1.759372e+01 // relaxed (2 iterations)
VCycle top 4, cycle 0, current 1, res_norm 1.234398e+01 // restricted
VCycle top 4, cycle 0, current 1, res_norm 4.728777e+00 // relaxed (2 iterations)
VCycle top 4, cycle 0, current 0, res_norm 3.343750e+00 // restricted
// coarsest grid
VCycle top 4, cycle 0, current 0, res_norm 0.000000e+00 // solved
// UP
VCycle top 4, cycle 0, current 1, res_norm 3.738426e+00 // prolonged
VCycle top 4, cycle 0, current 1, res_norm 0.000000e+00 // relaxed (many iterations)
VCycle top 4, cycle 0, current 2, res_norm 1.509429e+01 // prolonged (loosing digits)
VCycle top 4, cycle 0, current 2, res_norm 2.512148e-15 // relaxed (many iterations)
VCycle top 4, cycle 0, current 3, res_norm 4.695979e+01 // prolonged (loosing digits)
VCycle top 4, cycle 0, current 3, res_norm 0.000000e+00 // relaxed (many iterations)
VCycle top 4, cycle 0, current 4, res_norm 1.469312e+02 // prolonged (loosing digits)
VCycle top 4, cycle 0, current 4, res_norm 9.172812e-24 // relaxed (many iterations)

Ich bin mir nicht sicher, ob pro Zyklus nur wenige Stellen gewonnen werden können oder ob dies auf einen Fehler bei der Interpolation in das feine Gitter hinweist. Wenn es der letztere Fall ist, wie kann der LDC die Restverhältnisse von ~ 0,03 erreichen, wenn immer 2 Relaxationen verwendet werden?

Silpion
quelle

Antworten:

7

Ich kenne Ihre Antwort nicht direkt, da ich hauptsächlich FAS anstelle von Korrektur verwende, da ich Multigrid für nichtlineare Probleme mache, aber einige Gedanken, die Sie untersuchen können:

  • Sie wenden ein lineares Korrekturschema auf ein lineares Problem an, daher ist es nicht schockierend, dass es sehr gut funktioniert.

  • Berücksichtigen Sie Ihre Randbedingungen: Stellen Sie sicher, dass Sie sie korrekt ausführen, und beachten Sie auch, dass komplizierte BCs im Grobgitter völlig anders aussehen können, sodass Korrekturen dort nicht so nützlich sind.

  • Überprüfen Sie Ihre Behandlung des Quellbegriffs. Ich erinnere mich, dass ich in der Verlängerungsphase, die mit diesem Begriff zusammenhängt, etwas vermasselt habe, als ich ihn für Poisson geschrieben habe.

  • Ich habe noch nie die Notwendigkeit gesehen, auf dem gröbsten Gitter zur Konvergenz zu iterieren. Eine Lösung hängt davon ab, ob der Rest des feinen Gitters korrekt ist, was nicht der Fall ist. Sie versuchen, diese Fehler aus der Domäne zu entfernen / zu glätten. Wenn Sie in einer frühen Iteration vollständig auf dem gröbsten Raster konvergiert sind, ist Ihre Lösung natürlich ziemlich weit von der richtigen Feinrasterlösung entfernt, da Ihre Residuen dort nicht auf dem neuesten Stand sind. Dies ist mit ziemlicher Sicherheit der Grund, warum in der Verlängerungsphase Residuen auftauchen.

  • Versuchen Sie auch einen Relaxationsfaktor für die Restriktions- und Verlängerungsoperatoren, z. B. 0,75.

Wenn es hilft, sah meine FAS-Resthistorie für ein Poisson-Problem mit einem einzelnen Gitter über volle 7-V-Zyklen so aus. Ich glaube, der Relaxationsfaktor betrug 0,75, und ich verwendete ein dreistufiges RK-Schema als Glättung mit einer einzelnen Iteration auf jeder Gitterebene.

res Geschichte

Aurelius
quelle
Vielen Dank für Ihre Antwort. Der lineare Fall und der einfache BC (quadratischer Rand = 0) sind nur der erste Schritt. Das Testen realer Fälle wird durchgeführt, nachdem die "einfachen" Einstellungen funktionieren. Ich bin mir nicht sicher, ob ich verstehe, was Sie mit einem Entspannungsfaktor für Einschränkung und Verlängerung meinen. Ich verwende derzeit die bilineare Interpolation zur Verlängerung und die Halbgewichtung zur Einschränkung.
Silpion
uh:=uh+αIHh(uHIhHuh)0<α<1
(1α)
@ Aurelius Sie erwähnen, dass eine Konvergenz im Grobgitter nicht erforderlich ist. Ich stimme Ihrer Argumentation zu, aber Konvergenzbeweise in der Literatur (für den linearen Fall) setzen voraus, dass die Grobgitterlösung genau ist. Mir ist keine Referenz (für den linearen oder nichtlinearen Fall) bekannt, in der angegeben wird, dass die Grobgitterlösung nicht genau sein sollte, und ich habe mich gefragt, ob Sie eine Referenz dafür zitieren könnten. Ich wäre sehr daran interessiert, dies selbst zu sehen
Keeran Brabazon
@KeeranBrabazon Ich habe auch keine Referenz dafür, und ich bin ehrlich gesagt nicht genau mit den Details von Konvergenznachweisen für Multigrid vertraut. Ich würde vorschlagen, nach früher Literatur zu suchen, die diesen Entspannungsfaktor einführt. Dieser Faktor ist allen modernen Multigrid-Implementierungen gemeinsam, die ich gesehen habe, und es ist intuitiv wahr, dass er nicht benötigt würde, wenn genaue Kurslösungen notwendig / wünschenswert wären. Für einen intuitiven Beweis stelle ich mir nur vor, wie die Randbedingungen für das gröbste Gitter gegen das feinste aussehen. Es ist leicht vorstellbar, dass sie sehr unterschiedliche Lösungen schaffen.
Aurelius
6

IhHI^hHuhuh(uHIhHuh)I^hHuh

Spektral erfordert die Zustandsbeschränkung nur eine hohe sekundäre Ordnung (genaue Erhaltung niedriger Frequenzen), aber die primäre Ordnung (Aliasing hoher Frequenzen) spielt keine Rolle. Die Injektion hat die Primärordnung 0 und die unendliche Sekundärordnung. In der Zwischenzeit muss die Restrestriktion sowohl in der Primär- als auch in der Sekundärordnung positiv sein (zumindest). Siehe Abschnitt 4.3 des Achi Brandt Multigrid Guide .

Beim Entwerfen von MG-Methoden ist es auch gut, Fehler anstelle von Residuen zu betrachten und sicherzustellen, dass Sie die Norm angemessen gewichten.

Jed Brown
quelle
Gute Punkte, und ich hatte etwas in dieser Richtung nicht erwähnt. Ein wichtiger Aspekt des praktischen Einsatzes von Multigrid ist die Wahl des Glätters: Sie möchten einen, der Hochfrequenzfehler so schnell wie möglich dämpft und das von Ihnen beschriebene Problem behebt.
Aurelius
@ Aurelius Aus dem bereitgestellten Protokoll können Sie ersehen, dass der Glatter nicht das Problem ist. Denken Sie daran, dass Silpion denselben Glatter verwendet wie für die Fehlerkorrektur MG, die ordnungsgemäß konvergiert.
Jed Brown
>0.8
1

uoldH=IhHuh

uhuh+IHh(uHIhHuh)=uh+IHh(uHuoldH)

H2HuoldHuoldH

Silpion
quelle