Jakich wskazówek powinienem użyć, szukając dobrych metod przygotowania do określonego problemu?

19

W przypadku rozwiązania dużych układów liniowych metodami iteracyjnymi często interesujące jest wprowadzenie wstępnego kondycjonowania, np. Zamiast tego rozwiąż , gdzie jest tutaj stosowane do lewego wstępnego kondycjonowania układu . Zazwyczaj powinniśmy mieć ten i zapewnić podstawę (znacznie bardziej) wydajnego rozwiązania lub zmniejszenia zasobów obliczeniowych (np. Pamięci) w porównaniu z rozwiązaniem oryginalnego systemu ( tj. gdy ). Jednak jakich wskazówek powinniśmy użyć, aby wybrać warunek wstępny? Jak praktycy robią to ze względu na swój konkretny problem?ZAx=bM.-1(ZAx=b)M.M1A1M=A

Allan P. Engsig-Karup
źródło
1
Nawet w przypadku jednej szczególnej klasy równań wymagałoby to bardzo długiej i szczegółowej odpowiedzi ...
Jack Poulson
Powinno być możliwe zaproponowanie strategii heurystycznych dotyczących sposobu wyboru warunków wstępnych. Na przykład, biorąc pod uwagę problem, co praktycy robią w praktyce, aby znaleźć dobrego warunku wstępnego? Po prostu zacznij od podstawowej diagonalnej metody kondycjonowania opartej na wydobywaniu przekątnej z ? lub? A
Allan P. Engsig-Karup
4
Zamierzam skierować @MattKnepley i powiem, że właściwym działaniem jest przeszukanie literatury. Jeśli to się nie powiedzie, wypróbuj wszystkie łatwo dostępne opcje na dość dużym problemie. Jeśli to się nie powiedzie, zastanów się głęboko nad fizyką i tym, jak możesz tanio znaleźć przybliżone rozwiązanie problemu i użyj go jako warunku wstępnego.
Jack Poulson
@JackPoulson: Ponieważ to pytanie jest podobne do tego, którego należy użyć rzadkiego solvera systemu liniowego? i Jak wybrać skalowalny solver liniowy , wydaje mi się na ten temat (choć szeroki). Ponieważ twój komentarz jest w zasadzie odpowiedzią, czy mógłbyś go przekonwertować na odpowiedź?
Geoff Oxberry
Rozpocząłem nagrodę za to pytanie, ale interesuje mnie również więcej pytań w tym stylu, które mogłyby być lepiej postawione lub ograniczone do określonej klasy problemów.
Aron Ahmadia,

Odpowiedzi:

17

Początkowo nie chciałem udzielać odpowiedzi, ponieważ zasługuje ona na bardzo długie leczenie i mam nadzieję, że ktoś jeszcze ją udzieli. Z pewnością mogę jednak przedstawić krótki przegląd zalecanego podejścia:

  1. Przeprowadź dokładne wyszukiwanie literatury.
  2. Jeśli to się nie powiedzie, wypróbuj każdy warunek wstępny, który ma sens, że możesz wziąć w swoje ręce. MATLAB, PETSc i Trilinos to miłe środowiska do tego.
  3. Jeśli to się nie powiedzie, powinieneś dokładnie przemyśleć fizykę swojego problemu i sprawdzić, czy można znaleźć tanie przybliżone rozwiązanie, być może nawet nieco zmienioną wersję problemu.

Przykładami 3 są przesunięte Laplacowskie wersje Helmholtza i ostatnia praca Jinchao Xu nad przygotowaniem operatora biharmonicznego u Laplacian.

Jack Poulson
źródło
Dzięki! Reszta tego komentarza spełnia minimalny limit znaków.
Geoff Oxberry
14

Inni już skomentowali kwestię wstępnego kondycjonowania tego, co nazywam macierzami „monolitycznymi”, tj. Na przykład dyskretną formę równania skalarnego, takiego jak równanie Laplace'a, równanie Helmholtza lub, jeśli chcesz je uogólnić, wartość wektorową równanie sprężystości. W przypadku tych rzeczy jasne jest, że multigrid (algebraiczny lub geometryczny) jest zwycięzcą, jeśli równanie jest eliptyczne, a dla innych równań nie jest tak jasne - ale coś takiego jak SSOR często działa dość dobrze (dla pewnego znaczenia "rozsądny").

Dla mnie dużym objawieniem było to, co zrobić z problemami, które nie są monolityczne, na przykład dla operatora Stokesa Kiedy zacząłem od analizy numerycznej jakieś 15 lat temu, myślę, że ludzie mieli nadzieję, że te same techniki będą mogły być zastosowane do takich matryc jak powyżej, a kierunkiem badań było albo wypróbowanie multigrid bezpośrednio, albo użycie uogólnień SSOR (używając „ wygładzacze punktowe ”jak Vanka) i podobne metody. Ale to zanikło, ponieważ nie działa zbyt dobrze.

(ZAbbT.0).

Zastąpiło to to, co początkowo nazywano „kondycjonerami opartymi na fizyce”, a później po prostu (a może dokładniej) „blokowymi kondycjonerami”, takimi jak Silvester i Wathen. Często opierają się one na eliminacjach bloków lub uzupełnieniach Schura, a ideą jest zbudowanie kondycjonera w taki sposób, aby można było ponownie użyć kondycjonerów dla poszczególnych bloków, o których wiadomo, że działają dobrze. W przypadku równania Stokesa, na przykład, kondycjoner Silvester / Wathen używa matrycy

(ZAb0bT.ZA-1b)-1
gdy zostanie użyty jako warunek wstępny w GMRES, spowoduje zbieżność dokładnie w dwóch iteracjach. Ponieważ jest trójkątny, inwersja jest również znacznie prostsza, ale nadal mamy problem z tym, co zrobić z blokami ukośnymi, i tam stosuje się przybliżenia: gdzie tylda oznacza zastąpienie dokładnej odwrotności przybliżeniem. Często jest to o wiele prostsze: ponieważ blok A jest operatorem eliptycznym, ~ A - 1
(ZA-1~b0(bT.ZA-1b)-1~)
ZAZA-1~jest dobrze aproksymowany na przykład przez wielosieciowy cykl V i okazuje się, że tutaj jest dobrze aproksymowane przez ILU macierzy masy.(bT.ZA-1b)-1~

Pomysł pracy z poszczególnymi blokami, które składają się na macierz i ponownego użycia kondycjonerów na pojedynczych okazał się niezwykle potężny i całkowicie zmienił nasze dzisiejsze zdanie na temat kondycjonowania układów równań. Jest to oczywiście istotne, ponieważ większość rzeczywistych problemów to w rzeczywistości układy równań.

Wolfgang Bangerth
źródło
1
Człowieku, tak, tak bardzo chciałem nagrody! ;-)
Wolfgang Bangerth,
W drugim akapicie: „Ale to zniknęło, ponieważ nie działa zbyt dobrze”. Czy możesz podać intuicję, dlaczego to nie działa zbyt dobrze? Czy istnieją okoliczności, w których może to działać?
Andrew T. Barker,
Powodem, dla którego bezpośrednie zastosowanie wielosieciowego zastosowania do całych systemów nie okazało się tak skuteczne, jest to, że gładsza funkcja musi zachować właściwości strukturalne równania, a osiągnięcie tego nie jest łatwe. Na przykład, jeśli chcesz zastosować wielosieciowość do równań Stokesa, musisz mieć wygładzenie, które przy zastosowaniu wektora wolnego od dywergencji daje wektor wolny od dywergencji. Istnieją takie wygładzacze dla Stokesa, ale nie jest to łatwe do zbudowania i zwykle odbiera jakość jako wygładzacz / solver. Zachowanie właściwości w bardziej ogólnych przypadkach staje się znacznie trudniejsze.
Wolfgang Bangerth
Jeśli chodzi o uogólnianie rzeczy takich jak Jacobi / SSOR / etc na systemy: większość z tych metod wymaga, aby diagonalne wpisy macierzy były niezerowe. To oczywiście nie dotyczy Stokesa. Tak więc następną najprostszą metodą jest nie oglądanie pojedynczych wierszy macierzy, ale bloków wierszy, np. Wszystkich wierszy dla DoF związanych z jednym wierzchołkiem. Są to tak zwane „wygładzacze punktów” (punkt jak w wierzchołku) i działają do pewnego stopnia, ale cierpią z powodu takiego samego pogorszenia wydajności, jak Jacobi / SSOR, gdy problemy stają się duże. Aby tego uniknąć, podmiot przygotowujący musi globalnie wymieniać informacje jak multigrid.
Wolfgang Bangerth
Multigrid jest znany jako nieskuteczny w rozwiązywaniu Helmholtza, ponieważ głównie dlatego, że tryby oscylacyjne o niskiej energii są trudne do wygładzenia lub reprezentacji w szorstkiej przestrzeni. Pracowano już nad wielosieciową falą, ale sformułowanie jest bardzo techniczne i nie jest w tym momencie dojrzałą metodologią. Należy zauważyć, że systemy niesymetryczne można również rozwiązać za pomocą tego rodzaju rozkładu bloków. W zależności od wyboru zmiennych (np. Prymitywny vs. konserwatywny) zmiana podstawy może być wymagana w warunku wstępnym, aby odsłonić zablokowaną strukturę.
Jed Brown
13

Jack podał dobrą procedurę znalezienia warunku wstępnego. Spróbuję odpowiedzieć na pytanie: „Co stanowi dobry warunek wstępny?”. Definicja operacyjna to:

ZAx=bM.-1ZA-1

nie daje nam to jednak żadnego wglądu w projektowanie warunków wstępnych. Większość warunków wstępnych opiera się na manipulowaniu spektrum operatora. Zasadniczo metody Kryłowa zbiegają się szybciej, gdy wartości własne są grupowane , patrz Iteracje macierzy lub Funkcje meromorficzne i algebra liniowa . Czasami możemy udowodnić, że wyniki wstępnego kondycjonowania to tylko kilka unikalnych wartości własnych, np . Uwaga na temat wstępnego kondycjonowania dla nieokreślonych układów liniowych .

Przykładem wspólnej strategii jest Multigrid. Relaksacyjne środki kondycjonujące (tutaj wygładzacze), takie jak SOR, usuwają składowe wysokiej częstotliwości w błędzie. Kiedy reszta jest rzutowana na grubą siatkę, składniki błędu niższej częstotliwości stają się wyższą częstotliwością i mogą zostać ponownie zaatakowane przez SOR. Ta podstawowa strategia leży u podstaw bardziej skomplikowanych wersji MG, takich jak AMG. Zauważ, że na dole solver musi dokładnie rozpoznać najniższe częstotliwości błędu.

Inna strategia polega na rozwiązaniu równania w małych podprzestrzeniach, co dokładnie robią solwery Kryłowa. W najprostszej postaci jest to metoda Kaczmarza lub metoda addytywnego Schwarza . Zaawansowany szczep teorii, Dekompozycja Domeny , koncentruje się na aproksymacji spektralnej błędu na interfejsie, ponieważ zakłada się, że domeny zostały rozwiązane dość dokładnie.

ZA

Matt Knepley
źródło
Dziękuję za odpowiedź. Wszelkie doświadczenia dotyczące tego, jak daleko powinniśmy się posunąć, aby faktycznie udowodnić, że wstępne kondycjonowanie działa w przypadku dużych systemów - i możliwe, że można to lub należy zrobić w praktyce. Z mojego doświadczenia wynika, że ​​w wielu systemach musimy polegać na intuicji, heurystyce itp.
Allan P. Engsig-Karup
Myślę, że intuicja idzie za daleko. To, co widzę w praktyce, jest dowodem na prosty system. Następnie argument, że jakaś modyfikacja powinna być niewrażliwa na parametr lub pewien rodzaj wariacji. Następnie eksperymenty numeryczne pokazujące, że działa nawet poza tym modelem zmienności.
Matt Knepley,