W jakich przypadkach zastosowania schematy wstępnego kondycjonowania addytywnego są lepsze od multiplikatywnych?

Zarówno w przypadku metod dekompozycji domen (DD), jak i metod wielosiatkowych (MG), można skomponować zastosowanie aktualizacji bloków lub zgrubnych korekt jako addytywne lub multiplikatywne . W przypadku solverów punktowych jest to różnica między iteracjami Jacobiego i Gaussa-Seidela. Multiplikatywną wygładzacz dla działającego jako S ( x o l d , b ) = x n e w stosuje się jako$Ax = b$$S(x^{old}, b) = x^{new}$

$x_{i+1} = S_n(S_{n-1}( ..., S_1(x_i, b) ..., b), b)$

a dodatek wygładzający jest stosowany jako

$x_{i+1} = x_{i} + \displaystyle\sum_{\ell = 0}^{n}\lambda_\ell(S_\ell(x_i, b) - x_i)$

dla pewnego tłumienia . Ogólny konsensus wydaje się być taki, że multiplikatywne wygładzacze mają znacznie szybsze właściwości zbieżności, ale zastanawiałem się: w jakich sytuacjach lepsza jest wydajność addytywnych wariantów tych algorytmów?$\lambda_i$

Mówiąc dokładniej, czy ktoś ma jakieś przypadki użycia, w których wariant dodatkowy powinien i / lub działa znacznie lepiej niż wariant multiplikatywny? Czy są tego teoretyczne powody? Większość literatury na temat wielosieciowego jest dość pesymistyczna co do metody addytywnej, ale jest ona tak często stosowana w kontekście DD jak addytywna Schwarz. Dotyczy to również znacznie bardziej ogólnego problemu komponowania solwerów liniowych i nieliniowych oraz tego, jaki rodzaj konstrukcji będzie działał dobrze i działał równolegle.

Metody addytywne ujawniają większą współbieżność. Są na ogół szybsze niż metody multiplikatywne, jeśli można użyć tej współbieżności. Na przykład, zgrubne poziomy wielosieciowego są zwykle ograniczone przez opóźnienia. Jeśli przeniesiesz gruboziarniste poziomy do mniejszych podkomunikatorów, możesz je rozwiązać niezależnie od poziomów dokładniejszych. Dzięki multiplikatywnemu schematowi wszystkie procy muszą czekać, aż zgrubne poziomy zostaną rozwiązane.

Ponadto, jeśli algorytm wymaga redukcji na każdym poziomie, wariant addytywny może być w stanie je łączyć, gdy metoda multiplikatywna jest zmuszona do sekwencyjnego ich wykonywania.

W przypadku problemów SPD metody addytywne są lepsze do wygładzania MG z kilku powodów, jak już wspomniano, i kilku innych:

@Article{Adams-02, 
author = {Adams, M.~F. and Brezina, M. and Hu, J. J. and Tuminaro, R. S.}, 
title = {Parallel multigrid smoothing: polynomial versus {G}auss-{S}eidel}, 
journal = {J. Comp. Phys.}, 
year = {2003}, 
volume = {188}, 
number = {2}, 
pages = {593-610} }

Metody multiplikatywne mają jednak właściwe właściwości spektralne od razu po wyjęciu z pudełka dla wygładzacza MG, to znaczy nie wymagają tłumienia. Może to być duża wygrana w przypadku problemów hiperbolicznych, w których wygładzanie wielomianowe nie jest zbyt przyjemne.

Powtórzę to, co powiedział @Jed: Metoda multiplikatywna zawsze zbiega się co najmniej tak samo jak metoda addytywna (asymptotycznie), więc wygrywasz tylko w oparciu o współbieżność, ale to zależy od architektury.