W metodzie takiej jak gmres lub bicgstab korzystne może być zastosowanie innej metody krylova jako warunku wstępnego. W końcu są łatwe do wdrożenia w sposób wolny od matrycy i w środowisku równoległym. Na przykład, jeden coul używa kilku (powiedzmy ~ 5) iteracji nieprzewidzianej bigcstab jako preontioner dla gmres, lub dowolnej innej kombinacji metod krylova. W literaturze nie znajduję wiele odniesień do takiego podejścia, więc spodziewam się, że dzieje się tak, ponieważ nie jest ono zbyt skuteczne. Chciałbym zrozumieć, dlaczego to nie jest skuteczne. Czy istnieją przypadki, w których jest to dobry wybór?
W moich badaniach interesuje mnie rozwiązanie trójwymiarowych problemów eliptycznych w środowisku równoległym (MPI).
linear-algebra
linear-solver
preconditioning
krylov-method
gmres
Christine Darcoux
źródło
źródło
Odpowiedzi:
Ciekawe, że to pytanie przyszło wczoraj, ponieważ właśnie skończyłem wczoraj wdrożenie, które to robi.
Moje tło
Na początek daj mi znać, że chociaż moje wykształcenie pochodzi z informatyki naukowej, wszystkie prace, które wykonałem od ukończenia studiów, w tym mój obecny doktorat. praca, zajmowała się elektromagnetyką obliczeniową. Sądzę więc, że nasze tła są nieco podobne, ponieważ wydaje się, że również patrzysz na fizykę (na podstawie swojego profilu).
FGMRES
Przede wszystkim to, czego szukasz, jak już wspomniał Guido Kanschat w komentarzu, nazywa się Elastyczne GMRES lub FGMRES. Odwołanie, w tym pseudokod, znajduje się w [1]. Chociaż czasami uważam, że numeryczne dokumenty SIAM są nieco trudne do odczytania, [1] (i większość innych prac Saada, w tym genialny [B1], najwyraźniej legalnie dostępny za darmo online) jest inny; artykuł jest fascynującą lekturą, bardzo czytelnie napisany i zawiera kilka dobrych przykładów i sugestii dotyczących zastosowań.
FGMRES jest łatwy do wdrożenia, szczególnie jeśli masz już działający PRAWO wstępnie przygotowany GMRES. Zwróć uwagę na słowo kluczowe PRAWO - jeśli masz LEWE wstępnie uwarunkowane GMRES, tzn. Jesteś przyzwyczajony do rozwiązywania MAx = Mb, musisz wprowadzić kilka modyfikacji. Porównaj [B1, algorytm 9.4 na str. 282] do [B1, algorytm 9.5, str. 284]. Możesz także znaleźć FGMRES w [B1, Algorytm 9.6, str. 287], ale naprawdę zachęcam do przeczytania [1], ponieważ jest krótki, dobrze napisany i wciąż zawiera wiele interesujących szczegółów.
Co to robi
FGMRES zasadniczo umożliwia zmianę warunków wstępnych dla każdej iteracji, jeśli chcesz. Jedną z aplikacji do tego jest to, że możesz użyć jakiegoś warunku wstępnego, który działa bardzo dobrze, gdy jesteś daleko od rozwiązania, a następnie przełączyć się na inny, gdy zbliżysz się. [2], którego nie przeczytałem szczegółowo, wydaje się omawiać coś podobnego do tego.
Jednak najciekawszą aplikacją w moim przypadku było to, że można użyć (wstępnie kondycjonowanego) GMRES jako warunku wstępnego dla FGMRES. To jest powód typowej nazwy FGMRES, „wewnętrzna-zewnętrzna GMRES”. „Zewnętrzne” odnosi się tutaj do solwera FGMRES, który (jako warunek wstępny) używa solwera „wewnętrznego”.
Jak dobre to jest w praktyce?
W moim przypadku działało to absolutnie doskonale. W wewnętrznej pętli „rozwiązuję” sformułowanie mojego problemu o zmniejszonej złożoności. Rozwiązanie to samo w sobie jest zbyt niedokładne dla naszego zastosowania, ale działa absolutnie świetnie jako warunek wstępny. Zwróć uwagę na „„ wokół ”rozwiązania” - nie ma potrzeby uruchamiania wewnętrznego solwera w celu uzyskania zbieżności, ponieważ szukasz jedynie przybliżonych przybliżeń. W moim przypadku przeszedłem ze 151 iteracji, każda kosztuje 64 sekundy, do 72 iteracji, każda kosztuje 79 sekund (użyłem stałej 5 iteracji w wewnętrznym GMRES). Jest to całkowita oszczędność godziny, bez utraty dokładności i bardzo małej pracy kodowania, ponieważ mieliśmy już działający GMRES, który właśnie rekurencyjnie wprowadziliśmy.
W przypadku niektórych zastosowań tych rzeczy, pokazując potencjalną wydajność, patrz [3] (który faktycznie używa trójpoziomowego FGMRES, więc FGMRES, z FGMRES jako wewnętrzną, z GMRES jako wewnętrzną-wewnętrzną) i [4], która może być zbyt aplikacja specyficzna dla twojego zastosowania, ale zawiera kilka interesujących przypadków testowych.
Bibliografia
[1] Y. Saad, „Elastyczny algorytm GMRES z wewnętrznym i zewnętrznym warunkiem wstępnym”, SIAM J. Sci. Comp., Vol. 14, nr 2, ss. 461–469, marzec 1993. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf
[2] D.-Z. Ding, R.-S. Chen i Z. Fan, „Wstępnie kondycjonowana elastyczna metoda GMRES SSR wewnętrzna-zewnętrzna do analizy MLFMM rozpraszania otwartych obiektów”, Progress In Electromagnetics Research, vol. 89, s. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf
[3] TF Eibert, „Niektóre wyniki rozproszenia obliczone techniką równania całka-powierzchnia i hybrydowymi technikami elementu skończonego-granicy-całki, przyspieszone wielopoziomową szybką metodą wielobiegunową”, IEEE Antennas and Propagation Magazine, vol. 49, nr 2, s. 61–69, 2007.
[4] Ö. Ergül, T. Malas i L. Gürel, „Rozwiązania problemów elektromagnetycznych na dużą skalę z wykorzystaniem iteracyjnego schematu wewnętrznego i zewnętrznego ze zwykłymi i przybliżonymi wielopoziomowymi szybkimi algorytmami wielobiegunowymi”, Progress In Electromagnetics Research, tom. 106, s. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf
[B1] Y. Saad, Iteracyjne metody dla rzadkich układów liniowych. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf
źródło
Taka zagnieżdżona metoda podprzestrzeni Kryłowa może w praktyce działać całkiem dobrze. Może to być interesujące dla niesymetrycznych układów liniowych, w których zrestartowany GMRES zastyga, a niezrestartowany GMRES jest zbyt drogi lub zużywa zbyt dużo pamięci. Trochę literatury:
źródło