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

12

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 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.

— Peter Brune
źródło

6

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.

— Jed Brown
źródło

Uznałem, że taką odpowiedź otrzymam, więc sądzę, że pójdę jeszcze dalej z pytaniem. Czy zdarzają się sytuacje, w których stosowane są metody dodatkowe, w tym DD i MG, ale także rozdzielanie w terenie (które można uznać za podobne do DD, ale w praktyce mogą mieć inne cechy) lub podział PDE jest w rzeczywistości lepszy pod względem wydajności, odporności lub stabilności niż wariant multiplikatywny?

— Peter Brune,

1

Multiplikatywne wersje wielu algorytmów muszą przechowywać więcej informacji, ale czasami zbiegają się mniej więcej tak szybko. Czasami warianty addytywne są symetryczne, ale może być znacznie więcej pracy, aby multiplikatywny symetryczny. Dzięki podświetleniu pola warunek wstępny może stać się bardziej przybliżony po dodaniu tych dodatkowych rozwiązań. Możemy to zademonstrować na przykładzie PETSc Stokesa, jeśli chcesz. Dodatek jest zawsze łatwiejszy do wektoryzacji / bardziej współbieżny, ale każda wygrana w wydajności jest związana z problemem i architekturą.

— Jed Brown,

5

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.

— Adams
źródło

0

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.

— Matt Knepley
źródło

Nie technicznie poprawne, widma macierzy iteracji dla powiedzmy Gaussa-Seidela nie są jednakowo lepsze od Jacobiego (np. Jedna wartość własna zostaje zabita jedną iteracją Jacobiego). Mark (jak wylogować się jako Jed ...)

— Jed Brown