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

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?$Ax=b$$M^{-1}(Ax=b)$$M$$M^{-1}\approx A^{-1}$$M=A$

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.

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.

$$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$$

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

$$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-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 - $$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$$ $A$$\widetilde{A^{-1}}$jest dobrze aproksymowany na przykład przez wielosieciowy cykl V i okazuje się, że tutaj jest dobrze aproksymowane przez ILU macierzy masy.$\widetilde{(B^T A^{-1} B)^{-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ń.

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

$A x = b$$M^{-1}$$A^{-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.

$A$