FAS-multigrid wolniej niż liniowa korekcja defektów?

Wdrożyłem solver wielosiatkowy V-Cycle przy użyciu zarówno liniowej korekcji defektów (LDC), jak i pełnego schematu aproksymacji (FAS).

Mój problem jest następujący: przy użyciu LDC reszta jest zmniejszana o współczynnik ~ 0,03 na cykl. Implementacja FAS również jest zbieżna z czynnikiem liniowym, ale współczynnik ten wynosi tylko ~ 0,58. Zatem FAS potrzebuje około 20 razy więcej cykli.

Większość kodu jest współdzielona, jedyną różnicą są obliczenia w dół / w górę, których używa LDC

dół: $u_H:=0,\quad b_H:=I_h^H(b_h-L_hu_h)$

w górę: $u_h:=u_h+I_H^hu_H$

i wykorzystuje FAS

dół: $u_H:=I_h^Hu_h,\quad b_H:=I_h^Hb_h+L_HI_h^Hu_h-I_h^HL_hu_h$

w górę: $u_h:=u_h+I_H^h(u_H-I_h^Hu_h)$

Moje ustawienie testowe pochodzi z „A Multigrid Tutorial, Second Edition”, str. 64, ma rozwiązanie analityczne

$u(x,y)=(x^2-x^4)(y^4-y^2) \quad$ z $x,y\in [0,1]^2$

a równanie $Lv=\Delta u=:b$ , wykorzystując typowy liniowy szablon 5 punktów jako Laplace'a-Operator $L$ . Początkowe domysły to $v=0$ .

Zmiana ustawienia testu, np. Na trywialne $u(x,y)=0$ przy początkowym zgadywaniu $v=1$ daje prawie takie same współczynniki konwergencji.

Ponieważ różni się tylko kod w dół / w górę, wyniki LDC są zgodne z książką, a FAS przynajmniej wydaje się działać, nie mam pojęcia, dlaczego jest tak wolniejszy w tym samym ustawieniu liniowym.

Jest jedno dziwne zachowanie zarówno w LDC, jak i FAS, którego nie mogę jeszcze wyjaśnić, a dzieje się tak tylko wtedy, gdy początkowe zgadywanie jest złe (np. ale również w moich pełnych eksperymentach z wieloma siatkami, w których interpolacja do nowej drobnej siatki zwiększa resztę z do ): Jeśli zwiększę liczbę relaksacji po korekcie do bardzo dużej liczby, tak że rozwiązanie zostanie rozwiązane z precyzją maszynową na grubej siatce, traci prawie wszystkie cyfry przy przejściu o jeden krok w górę do następnej drobnej siatki. $=0$ $10^{-15}$ $10^{-1}$

Ponieważ zdjęcie mówi więcej niż słowa:

// 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)

Nie jestem pewien, czy można uzyskać tylko kilka cyfr na cykl, czy też oznacza to błąd podczas interpolacji do dokładnej siatki. Jeśli tak jest w tym drugim przypadku, w jaki sposób LDC może osiągnąć ustalone przez księgę współczynniki resztkowe ~ 0,03, stosując zawsze 2 relaksacje?

multigrid Silpion
źródło

Odpowiedzi:

Nie znam bezpośrednio twojej odpowiedzi, ponieważ używam głównie FAS zamiast korekcji, ponieważ robię wiele siatki dla problemów nieliniowych, ale niektóre przemyślenia, na które możesz spojrzeć:

Stosujesz schemat korekcji liniowej do problemu liniowego, więc nie jest szokujące, że robi to bardzo dobrze.
Rozważ swoje warunki brzegowe: upewnij się, że robisz to poprawnie, a także zauważ, że skomplikowane BC mogą wyglądać zupełnie inaczej na grubej siatce, powodując, że korekty nie będą tak przydatne.
Dokładnie sprawdź sposób traktowania terminu źródłowego; Pamiętam, jak spieprzyłem coś w fazie przedłużania związanej z tym terminem, kiedy pisałem to dla Poissona.
Nigdy nie widziałem potrzeby iteracji w celu konwergencji na najgrubszej siatce. Rozwiązanie zależy od tego, czy drobna pozostałość siatki jest poprawna, co nie jest. Próbujesz wypchnąć te błędy z domeny / wygładzić je. Jeśli jesteś w pełni zintegrowany na najgrubszej siatce we wczesnej iteracji, twoje rozwiązanie jest naturalnie dość dalekie od prawidłowego dokładnego rozwiązania siatki, ponieważ twoje resztki nie są aktualne. Jest to prawie na pewno powód, dla którego widać, że pozostałości podskakują w fazie przedłużania.
Spróbuj także współczynnika relaksacji dla operatorów ograniczenia i przedłużenia, powiedzmy 0,75.

Jeśli to pomaga, tak wyglądała moja historia szczątkowa FAS dla problemu poissona z wykorzystaniem pojedynczej sieci w pełnych cyklach 7 V. Uważam, że współczynnik relaksacji wynosił 0,75, i użyłem 3-etapowego schematu RK jako płynniejszej z pojedynczą iteracją na każdym poziomie siatki.

historia res

Aureliusz
źródło

Dzięki za odpowiedź, przypadek liniowy i prosty BC (kwadratowa ramka = 0) to tylko pierwszy krok, testowanie rzeczywistych przypadków zostanie wykonane po „łatwych” ustawieniach. Nie jestem pewien, czy rozumiem, co masz na myśli przez czynnik relaksacyjny dla ograniczenia i przedłużenia. Obecnie używam interpolacji dwuliniowej dla przedłużenia i półważenia dla ograniczenia.

Silpion,

Przez relaksację rozumiem, że dla twojego etapu przedłużenia go na: gdzie jest współczynnikiem relaksacji. Zasadniczo im bardziej skomplikowane rozwiązanie, tym niższy musi być ten czynnik. W rozwiązaniach z dużą ilością nieciągłości czasami muszę obniżyć to do około 0,6, ale ogólnie 0,75-0,85 działa.

u_{h} := u_{h} + α I_{H}^{h} (u_{H} - I_{h}^{H} u_{h})

$u_h:=u_h+\alpha I_H^h(u_H-I_h^Hu_h)$

0 < α < 1

$0< \alpha <1$

Aureliusz

Dobrze wiedzieć. W moim ustawieniu spowalnia to tylko współczynnik konwergencji o ale będę o tym pamiętać podczas testowania bardziej złożonych danych.

(1 - α)

$(1-\alpha)$

Silpion,

@Aurelius wspominasz, że zbieganie na grubej siatce nie jest konieczne. Zgadzam się z twoim rozumowaniem, ale dowody zbieżności w literaturze (dla przypadku liniowego) zakładają, że rozwiązanie grubej siatki jest dokładne. Nie znam żadnego odniesienia (dla przypadku liniowego lub nieliniowego), w którym stwierdzono, że rozwiązanie zgrubnej siatki nie powinno być dokładne, i zastanawiałem się, czy możesz przytoczyć odniesienie do tego? Byłbym bardzo zainteresowany widząc to sam

Keeran Brabazon

@KeeranBrabazon Nie mam też odniesienia do tego i szczerze mówiąc, nie jestem do końca zaznajomiony ze szczegółami dowodów na zbieżność dla wielu sieci. Proponuję poszukać wczesnej literatury, która wprowadza ten czynnik relaksacyjny. Ten czynnik jest wspólny dla wszystkich współczesnych wdrożeń opartych na wielu sieciach, które widziałem, i intuicyjnie jest prawdą, że nie byłoby potrzebne, gdyby dokładne / pożądane były rozwiązania kursu. Dla intuicyjnego dowodu wyobrażam sobie, jak wyglądają warunki brzegowe dla najgrubszej siatki w porównaniu z najlepszą. Łatwo jest sobie wyobrazić, że tworzą bardzo różne rozwiązania.

Aurelius,

Jeśli używasz dyskretyzacji zorientowanej na wierzchołki, wówczas ograniczeniem stanu powinno być zastrzyk, a nie pełne ograniczenie resztkowe, które wydaje się stosować. Oznacza to, że zastąpi z gdy ograniczenie stanu. Zastosowanie pełnego ważenia ograniczenia dla stanu powoduje aliasing składowych wysokiej częstotliwości stanu, który po zastosowaniu powoduje powstanie nowego szumu na taką samą skalę jak poprzednio zgrubna korekta (warunki brzegowe są szczególnie prawdopodobnymi winowajcami tego efektu). Użyj zastrzyku, , a ten problem powinien zniknąć. $I_h^H$ $\hat I_h^H$ $u^h \gets u^h (u^H - I_h^H u^h)$ $\hat I_h^H u^h$

Widmowo, ograniczenie stanu wymaga jedynie wysokiego rzędu wtórnego (dokładne zachowanie niskich częstotliwości), ale pierwotny porządek (aliasing wysokich częstotliwości) nie ma znaczenia. Zastrzyk ma pierwotny rząd 0 i nieskończony rząd wtórny. Tymczasem ograniczenie resztkowe musi być zarówno pierwotne, jak i wtórne, aby było dodatnie (przynajmniej). Zobacz rozdział 4.3 Przewodnika po wielu sieciach Achi Brandta .

Projektując metody MG, dobrze jest również spojrzeć na błąd, a nie na pozostałości, i upewnić się, że odpowiednio wyważasz normę.

Jed Brown
źródło

Dobre punkty, a ja nie wspomniałem o czymś podobnym. Jednym ważnym aspektem praktycznego zastosowania multigrid jest wybór bardziej płynnego: chcesz taki, który jak najszybciej tłumi błędy wysokiej częstotliwości, co rozwiązuje opisany problem.

Aureliusz

@Aurelius Z dostarczonego dziennika widać, że wygładzenie nie stanowi problemu. Przypomnij sobie, że Silpion używa tej samej wygładzającej, co w przypadku korekcji defektu MG, która jest odpowiednio zbieżna.

Jed Brown

Dzięki za link do Przewodnika Multigrid Brandta, przeczytam go dokładnie po ukończeniu Samouczka Multigrid Brigga. Rozwiązałem problem teraz (zobacz inną odpowiedź), ale obecnie używam pełnej wagi zarówno dla ograniczeń stanu, jak i resztkowych. Wydaje się, że zastosowanie iniekcji nie działa w moim ustawieniu, współczynniki resztkowe zmieniają się na i zarówno normy resztkowe, jak i błąd L2 przestają wkrótce spadać. Czy masz jakieś pomysły, dlaczego zastrzyk się nie udaje?

> 0.8

$>0.8$

Silpion,

Rozwiązałem teraz problem. I przechowywano , gdy spada podczas V cyklu ponownego wykorzystania później w $u_{old}^H=I_h^Hu^h$

$u^h\leftarrow u^h+I_H^h(u^H-I_h^Hu^h)=u^h+I_H^h(u^H-u_{old}^H)$ .

Problem polegał na tym, zanim ponownie zszedłem z do , był zrelaksowany na miejscu . Przechowywanie kopii przed etapami relaksacji pomogło. Ponieważ był wymagany tylko w FAS, nie pojawił się w obliczeniach liniowych. $H$ $2H$ $u_{old}^H$ $u_{old}^H$

Silpion
źródło