Czy zwykle w Multigrid nie ma sprawdzania zbieżności?

12

Właśnie przeczytałem rozdział 3 w „A Multigrid Tutorial” Briggsa / Hensona / McCormicka, link .

Tekst dotyczy cykli wielosieciowych, takich jak cykl V, cykl mu, FMG. Co przykuło moją uwagę: w większości procedur iteracyjnych sprawdza się, czy osiągnął pożądaną tolerancję / dokładność, a jeśli tak, to procedura się kończy. Ale Briggs / Henson / McCormick nie używają żadnego sprawdzania zbieżności w przedstawionych schematach. Liczba iteracji i rekurencji jest po prostu zakodowana na stałe i należy ufać, że schemat się zbiegnie.

Jak to się zwykle robi w Multigrid? Czy zwykle liczba iteracji / rekurencji jest po prostu zakodowana? Naprawdę obawiam się, że albo zmarnuję dużo czasu na obliczenia, ponieważ jestem zbyt precyzyjny, az drugiej strony dokładność będzie niska w wielu przypadkach, gdy wybiorę mniejszą liczbę iteracji / rekurencji.

Michał
źródło
Brak odpowiedzi na to pytanie jest dla mnie naprawdę zaskakujący. Czy na pewno jest tu kilku bardzo aktywnych użytkowników, którzy mają dość duże doświadczenie w pracy w sieci i środowisku produkcyjnym?
Doug Lipiński
2
Myślę, że problem polega na tym, że obecnie multigrid jest rzadko używany jako solver (z powodu braku ogólnej teorii konwergencji), ale raczej jako warunek wstępny dla bardziej ugruntowanej metody iteracyjnej, takiej jak CG lub GMRES. W tym kontekście nie jest konieczne sprawdzanie zbieżności dla wielu sieci, ponieważ zajmuje się tym iteracja zewnętrzna.
Christian Clason

Odpowiedzi:

4

Tak, normalne jest, że nie ma kontroli zbieżności w MG z kilku powodów. Po pierwsze, jeśli użyjesz innej liczby iteracji przy każdym przejściu, operator MG nie będzie już liniowy i będziesz musiał użyć czegoś takiego jak FGMRES jako akcelerator, który może pomieścić nieliniowy warunek wstępny. Po drugie, FMG to dokładny solver (zmniejsza błąd poniżej błędu dyskretyzacji), gdy działa, więc sprawdzenie zbieżności wprowadza kosztowną synchronizację do algorytmu. Zazwyczaj sprawdzasz na końcu tylko po to, by zweryfikować zbieżność.

Matt Knepley
źródło
Czy masz jakieś źródła, aby to zrobić? Obecnie twoja odpowiedź i druga najczęściej głosowana odpowiedź są ze sobą sprzeczne.
Doug Lipiński
1) Książka Saada jest najlepszym odniesieniem do korzystania z FGMRES w celu dostosowania się do zmieniającego się warunku wstępnego: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) Uważam, że dowód na to, że FMG zmniejsza błąd poniżej błędu dyskretyzacji przy wystarczająco silnym działaniu Cykl V jest w Trottenberg i Osterlee, ale powielam dowód w mojej książce: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf
Matt Knepley
4

Absolutnie nie. Aby wybrać jeden przykład, książka Multigrid ma wykres na stronie 53 (rysunek 2.10), który pokazuje spadek wartości rezydualnej w funkcji liczby cykli V lub W. Zatrzymałbyś jazdę na rowerze, gdy jesteś zadowolony z wielkości pozostałości.

Przyczyną twojego zamieszania może być to, że niektóre opisy opisują tylko pojedynczy cykl V. W niektórych ograniczonych przypadkach, ponieważ multigrid jest tak potężną techniką, może to wygenerować odpowiednie rozwiązanie. Również multigrid może być użyty jako warunek wstępny . W takim przypadku multigrid jest tylko akceleratorem, a kontrola zbieżności odbywa się na wyższym poziomie. Ale kontrola zawsze powinna się gdzieś zdarzyć.

Damaszek Stal
źródło
1
Czy masz jakieś źródła, aby to zrobić? Obecnie twoja odpowiedź i druga najczęściej głosowana odpowiedź są ze sobą sprzeczne.
Doug Lipiński
1

W Multigrid używanym jako solver , jako kryterium zatrzymania stosuje się zwykle względną normę wartości rezydualnej. Gdy zmniejszysz ten współczynnik - dokładność rozwiązania powinna wzrosnąć. Ponadto na najgrubszym poziomie badacze robią różne rzeczy:

  1. albo rozwiąż za pomocą solwera bezpośredniego (bez zbieżności)
  2. używaj stałych iteracji (bez zbieżności)
  3. użyj kolejnej różnicy między iteracjami jako kryterium konwergencji (niezbyt dobra metoda, ponieważ możesz być daleko od rozwiązania)
  4. Ponownie zastosuj względną normę resztkową jako kryterium zatrzymania.

Metoda 2 wymieniona powyżej na najgrubszym poziomie jest dobra, gdy Multigrid jest używany jako kondycjoner wstępny (eksperci od Multigrid tutaj mogą komentować - jestem początkujący).

Tak więc ogólnie stosowana jest konwergencja .

Gaurav Saxena
źródło