In Methoden wie gmres oder bicgstab könnte es attraktiv sein, eine andere Krylov-Methode als Vorkonditionierer zu verwenden. Schließlich sind sie einfach matrixfrei und in einer parallelen Umgebung zu implementieren. Zum Beispiel kann man einige Iterationen (sagen wir ~ 5) von nicht aufbereiteten Bigcstab als Vorbedingung für gmres oder jede andere Kombination von Krylov-Methoden verwenden. Ich finde in der Literatur nicht viel Bezug zu solchen Ansätzen, daher gehe ich davon aus, dass dies daran liegt, dass sie nicht sehr effektiv sind. Ich würde gerne verstehen, warum es nicht effizient ist. Gibt es Fälle, in denen es eine gute Wahl ist?
In meiner Forschung interessiere ich mich für die Lösung von 3d elliptischen Problemen in einer parallelen (mpi) Umgebung.
quelle
Antworten:
Interessant, dass diese Frage gestern kam, da ich gestern gerade eine Implementierung beendet habe, die dies tut.
Mein hintergrund
Lassen Sie mich zunächst wissen, dass ich zwar einen wissenschaftlichen Hintergrund habe, aber alle Arbeiten, die ich seit meinem Abschluss geleistet habe, einschließlich meiner aktuellen Promotion. Arbeit, hat in der rechnerischen Elektromagnetik gewesen. Ich denke, unsere Hintergründe sind sich einigermaßen ähnlich, da Sie sich anscheinend auch mit Physik befassen (basierend auf Ihrem Profil).
FGMRES
Zunächst heißt das, was Sie suchen, wie Guido Kanschat bereits in einem Kommentar erwähnt hat, Flexible GMRES oder FGMRES. Die Referenz, einschließlich Pseudocode, befindet sich in [1]. Zwar finde ich numerische SIAM-Artikel manchmal etwas schwer zu lesen, [1] (und die meisten anderen Arbeiten von Saad, einschließlich des brillanten [B1], das online anscheinend kostenlos erhältlich ist), unterscheiden sich jedoch. Das Papier ist eine faszinierende Lektüre, sehr klar geschrieben und mit ein paar schönen Beispielen und Anwendungsvorschlägen versehen.
FGMRES ist einfach zu implementieren, insbesondere wenn Sie bereits ein funktionsfähiges RIGHT-vorkonditioniertes GMRES haben. Notieren Sie sich hier das Schlüsselwort RECHTS - wenn Sie ein LEFT-vorkonditioniertes GMRES haben, dh wenn Sie es gewohnt sind, MAx = Mb zu lösen, müssen Sie einige Änderungen vornehmen. Vergleiche [B1, Algorithmus 9.4 auf S. 282] bis [B1, Algorithmus 9.5, pg. 284]. Sie finden die FGMRES auch in [B1, Algorithmus 9.6, S. 287], aber ich möchte Sie wirklich ermutigen, [1] zu lesen, da es kurz und gut geschrieben ist und noch viele interessante Details enthält.
Was tut es
Mit FGMRES können Sie grundsätzlich bei jeder Iteration die Vorkonditionierer wechseln, wenn Sie dies wünschen. Eine der Anwendungen dafür ist, dass Sie einen Vorkonditionierer verwenden können, der sehr gut funktioniert, wenn Sie weit von der Lösung entfernt sind, und dann zu einem anderen wechseln, wenn Sie näher kommen. [2], das ich nicht im Detail gelesen habe, scheint etwas Ähnliches zu diskutieren.
Die interessanteste Anwendung in meinem Fall war jedoch, dass Sie ein (vorkonditioniertes) GMRES als Vorkonditionierungsmittel für Ihr FGMRES verwenden konnten. Dies ist der Grund für den typischen Namen für FGMRES, "Inner-Outer-GMRES". Hier bezieht sich "äußerlich" auf den FGMRES-Löser, der (als Vorkonditionierer) einen "inneren" Löser verwendet.
Wie gut ist das in der Praxis?
In meinem Fall hat das absolut genial geklappt. In der inneren Schleife "löse" ich eine weniger komplexe Formulierung meines Problems. Diese Lösung ist für sich genommen viel zu ungenau für unseren Einsatz, eignet sich aber hervorragend als Vorkonditionierer. Beachten Sie das "um" lösen "- es ist nicht erforderlich, den inneren Löser zur Konvergenz auszuführen, da Sie nur nach groben Annäherungen suchen. In meinem Fall habe ich 151 Iterationen zu je 64 Sekunden und 72 Iterationen zu je 79 Sekunden verwendet (ich habe feste 5 Iterationen im inneren GMRES verwendet). Das ist eine Gesamteinsparung von einer Stunde ohne Genauigkeitsverlust und mit sehr wenig Codierungsaufwand, da wir bereits ein funktionierendes GMRES hatten, das wir gerade rekursiv gemacht haben.
Für einige Anwendungen dieses Materials, in denen die potenzielle Leistung demonstriert wird, siehe [3] (der tatsächlich ein dreistufiges FGMRES verwendet, also FGMRES mit FGMRES als innerem, mit GMRES als innerem-innerem) und [4], die möglicherweise auch verwendet werden anwendungsspezifisch, enthält aber einige interessante Testfälle.
Verweise
[1] Y. Saad, "Ein flexibler vorkonditionierter GMRES-Algorithmus von innen nach außen", SIAM J. Sci. Comp., Vol. 14, nein. 2, S. 461–469, März 1993. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf
[2] D.-Z. Ding, R.-S. Chen und Z. Fan, "SSOR vorkonditionierte innere-äußere flexible GMRES-Methode für die MLFMM-Analyse der Streuung offener Objekte", Progress In Electromagnetics Research, vol. 89, S. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf
[3] TF Eibert, „Einige Streuungsergebnisse, die mithilfe von Oberflächenintegralgleichungen und hybriden Finite-Elemente-Grenzintegral-Techniken berechnet wurden und durch die schnelle Multipolmethode auf mehreren Ebenen beschleunigt wurden“, IEEE Antennas and Propagation Magazine, vol. 49, nein. 2, S. 61–69, 2007.
[4] Ö. Ergül, T. Malas und L. Gürel, "Lösungen für elektromagnetische Großprobleme unter Verwendung eines iterativen Innen-Außen-Schemas mit gewöhnlichen und ungefähren schnellen Multilevel-Multipol-Algorithmen", Progress In Electromagnetics Research, vol. 106, S. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf
[B1] Y. Saad, Iterative Methoden für spärliche lineare Systeme. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf
quelle
Eine solche verschachtelte Krylov-Subraummethode kann in der Praxis recht gut funktionieren. Dies kann für nicht symmetrische lineare Systeme von Interesse sein, bei denen neu gestartetes GMRES stagniert und nicht neu gestartetes GMRES zu teuer ist oder zu viel Speicher verwendet. Einige Literatur:
quelle