Czy można zastosować metodę podprzestrzeni Kryłowa jako wygładzającą dla wielu sieci?

15

O ile mi wiadomo, solwery wielosieciowe używają iteracyjnych wygładzaczy, takich jak Jacobi, Gauss-Seidel i SOR, aby tłumić błąd przy różnych częstotliwościach. Czy zamiast tego można zastosować metodę podprzestrzeni Kryłowa (jak gradient sprzężony, GMRES itp.)? Nie sądzę, że są one klasyfikowane jako „wygładzacze”, ale można ich użyć do przybliżenia rozwiązania zgrubnej siatki. Czy możemy spodziewać się analogicznej zbieżności z rozwiązaniem, jak w przypadku standardowej metody wielosiatkowej? Czy to zależy od problemu?

Paweł
źródło

Odpowiedzi:

18

Tak, możesz, ale metody Kryłowa na ogół nie mają doskonałych właściwości wygładzających. Wynika to z faktu, że są ukierunkowane na całe spektrum w sposób adaptacyjny, który minimalizuje resztkową lub odpowiednią normę błędu. Zazwyczaj obejmuje to niektóre tryby niskiej częstotliwości (długiej fali), które dobrze radziłyby sobie z grubymi siatkami. Wygładzacze Krylowa sprawiają również, że cykl wielosiatkowy jest nieliniowy, więc jeśli wielosieciowy jest stosowany jako warunek wstępny dla zewnętrznej metody Kryłowa, metoda zewnętrzna powinna być „elastyczna” (np. GCR lub FGMRES).

Używanie wygładzaczy Krylova również znacznie zwiększa liczbę produktów punktowych, które należy obliczyć, co staje się znaczącym wąskim gardłem równolegle. Jednak nawet przy tych nieatrakcyjnych właściwościach wygładzacze Kryłowa są czasem przydatne, szczególnie w przypadku trudnych problemów, w których dobre operatory interpolacji nie są dostępne.

λmaxre-1ZAre-1ZA(0,1λmax,1.1λmax)15510) GMRES lub CG są używane do oszacowania , więc użytkownik nie musi sam ich obliczać. Oszacowanie jest również wykorzystywane przez niektóre algebraiczne metody wielosiatkowe do wybierania strategii zgrubnych.λmaxλmax

Adams, Brezina, Hu i Tuminaro (2003) to niezły artykuł na temat równoległego i algorytmicznego działania wygładzaczy wielomianowych. Zauważ, że wygładzacze wielomianowe są zwykle mniej skuteczne (i / lub trudne do sformułowania) w przypadku problemów niesymetrycznych, w którym to przypadku prawdopodobnie będziesz chciał użyć Gaussa-Seidela lub bardziej wyrafinowanych (blokowych / rozproszonych) schematów relaksacyjnych.

Jed Brown
źródło
Czy możesz zasugerować dobry zasób na temat wygładzaczy wielomianowych i / lub krylovowych? Tak naprawdę nigdy o tym nie słyszałem :)
Paweł
@JedBrown: Czy masz na myśli „eliptyczny” w sensie PDE lub postaci dwuliniowej (tj. Czy masz na myśli, że wszystkie wartości własne operatora lub głównego symbolu są dodatnie?)? Zakładam to drugie, ponieważ mówisz o punktowym bloku Jacobi.
Jack Poulson
Paweł Dodałem odniesienie. @Jack Ściśle mówiąc, dyskretnym operatorem powinien być SPD, ale w praktyce metody mają tendencję do działania, o ile widmo nie jest zbyt słabo rozłożone.
Jed Brown