Jaka jest przewaga technologii wielosiatkowej nad warunkami wstępnymi dekompozycji domen i odwrotnie?

Jest to głównie ukierunkowane na eliptyczne PDE w domenach wypukłych, dzięki czemu mogę uzyskać dobry przegląd tych dwóch metod.

Metody dekompozycji domen wielopoziomowych i wielopoziomowych mają tyle wspólnego, że każda z nich może być zwykle zapisana jako szczególny przypadek drugiej. Ramy analizy są nieco inne, co wynika z różnych filozofii każdej dziedziny. Ogólnie rzecz biorąc, metody wielosiatkowe wykorzystują średnie szybkości zgrubienia i proste wygładzanie, podczas gdy metody dekompozycji domen wykorzystują niezwykle szybkie zgrubienie i silne wygładzanie .

Multigrid (MG)

Multigrid wykorzystuje średnie szybkości zgrubienia i osiąga solidność poprzez modyfikację interpolacji i wygładzanie. W przypadku problemów eliptycznych operatory interpolacji powinny być „niskoenergetyczne”, tak aby zachowały prawie zerową przestrzeń operatora (np. Tryby bryły sztywnej). Przykładem geometrycznego podejścia do tych interpolantów o niskiej energii jest Wan, Chan, Smith (2000) , w porównaniu do algebraicznej konstrukcji wygładzonej agregacji Vaněk, Mandel, Brezina (1996) (równoległe implementacje w ML i PETSc przez PCGAMG, zamiennik dla Prometheus ) . Książka Trottenberga, Oosterlee i Schüllera stanowi dobre ogólne odniesienie do metod Multigrid.

Większość wygładzaczy wielosiatkowych wymaga punktowego rozluźnienia, albo addytywnie (Jacobi), albo multiplikacyjnie (Gauss Seidel). Odpowiadają one drobnym problemom Dirichleta (pojedynczy węzeł lub pojedynczy element). Pewną adaptacyjną spektralność, odporność i wektoryzację można uzyskać za pomocą wygładzaczy Chebysheva , patrz Adams, Brezina, Hu, Tuminaro (2003) . W przypadku problemów niesymetrycznych (np. Transportowych) generalnie konieczne są multiplikatywne wygładzacze, takie jak Gauss-Seidel, i można zastosować interpolanty przy odwróceniu. Alternatywnie, wygładzacze problemów z punktem siodłowym i problemami z falami sztywnymi można konstruować poprzez przekształcenie za pomocą inspirowanych przez Schura „wstępnych bloków wstępnych” lub powiązanego z nimi „rozproszonego rozluźnienia” w układy, w których proste wygładzacze są skuteczne.

Wydajność podręczników dla wielu sieci odnosi się do rozwiązania problemu błędu dyskretyzacji w niewielkiej wielokrotności kosztu kilku ocen resztkowych, zaledwie czterech, na drobnej siatce. Oznacza to, że liczba iteracji do ustalonej tolerancji algebraicznej spada wraz ze wzrostem liczby poziomów. Równolegle szacowanie czasu obejmuje logarytmiczny termin powstały w wyniku synchronizacji wynikającej z hierarchii wielosieciowej.

Dekompozycja domeny (DD)

Metody dekompozycji pierwszej domeny miały tylko jeden poziom. Bez poziomu zgrubnego numer stanu kondycjonowanego operatora nie może być mniejszy niż $\mathcal O\big( \frac{L^2}{H^2}\big)$$L$$H$$\mathcal O\big( \frac{L^2}{hH} \big)$$h$$H/h$

Aby uzyskać optymalne lub quasi-optymalne wskaźniki konwergencji, konieczne jest zastosowanie wielu poziomów. Większość metod DD jest przedstawiana jako metody dwupoziomowe, a niektóre bardzo trudno jest rozszerzyć na więcej poziomów. Metody DD można zaklasyfikować jako nakładające się lub nie nakładające się.

Pokrywające się

Te metody Schwarz wykorzystują nakładanie się i zasadniczo oparte są na rozwiązywaniu problemów Dirichleta. Siłę metod można zwiększyć, zwiększając nakładanie się. Ta klasa metod jest zwykle solidna, nie wymaga lokalnej identyfikacji pustej przestrzeni lub modyfikacji technicznych w przypadku problemów z lokalnymi ograniczeniami (powszechnymi w inżynierii mechaniki brył), ale wymaga dodatkowej pracy (szczególnie w 3D) z powodu nakładania się. Ponadto w przypadku ograniczonych problemów, takich jak nieściśliwość, zwykle pojawia się stała inf-sup nakładającego się paska, co prowadzi do nieoptymalnych współczynników zbieżności. Nowoczesne metody nakładania się przy użyciu podobnych grubych przestrzeni do BDDC / FETI-DP (omówione poniżej) opracowali Dorhmann, Klawonn i Widlund (2008) oraz Dohrmann i Widlund (2010) .

Nie nakładają się

Metody te zwykle rozwiązują pewnego rodzaju problemy Neumanna, co oznacza, że ​​w przeciwieństwie do metod Dirichleta, nie mogą one pracować z globalnie złożoną matrycą, a zamiast tego wymagają niezmontowanych lub częściowo zmontowanych matryc. Najpopularniejsze metody Neumanna wymuszają ciągłość między poddomenami poprzez równoważenie przy każdej iteracji lub mnożniki Lagrange'a, które wymuszają ciągłość dopiero po osiągnięciu zbieżności. Wczesne metody tego rodzaju (równoważenie Neumanna-Neumanna i FETI) wymagają precyzyjnej charakterystyki pustej przestrzeni każdej subdomeny, zarówno w celu skonstruowania zgrubnego poziomu, jak i uczynienia problemów z subdomenami osobliwymi. Późniejsze metody (BDDC i FETI-DP) wybierają narożniki poddomeny i / lub momenty krawędzi / powierzchni jako zgrubne stopnie swobody. Zobacz Klawonn i Rheinbach (2007)do dogłębnej dyskusji na temat wyboru grubej przestrzeni dla elastyczności 3D. Mandel, Dohrmann i Tazaur (2005) wykazali, że BDDC i FETI-DP mają te same wartości własne, z wyjątkiem możliwych 0 i 1.

Więcej niż dwa poziomy

Większość metod DD jest przedstawiana tylko jako metody dwupoziomowe, a niektóre wybierają zgrubne przestrzenie, które są niewygodne w użyciu na więcej niż dwóch poziomach. Niestety, szczególnie w 3D, problemy z grubym poziomem szybko stają się wąskim gardłem, ograniczając rozmiary problemów, które można rozwiązać. Ponadto liczby warunków dla kondycjonowanych operatorów, szczególnie dla metod DD opartych na problemach Neumanna, mają tendencję do skalowania jako

$L$$L \le 4$$10^{12}$

Jest to doskonały napis, ale myślę, że powiedzenie, że (wielopoziomowe) DD i MG mają ze sobą wiele wspólnego, nie jest dokładne, a przynajmniej nie jest przydatne. Metody są bardzo różne i nie sądzę, aby wiedza specjalistyczna w jednym była bardzo przydatna w drugim.

Po pierwsze, obie społeczności używają różnych definicji złożoności: DD optymalizuje liczbę stanów wstępnie przygotowanych systemów, a MG optymalizuje złożoność pracy / pamięci. To duża podstawowa różnica - „optymalność” ma zupełnie inne znaczenie w tych dwóch kontekstach. Rzeczy nie zmieniają się, gdy dodajesz równolegle złożoność (chociaż otrzymujesz termin dziennika dodany w MG). Obie społeczności prawie mówią różnymi językami.

Po drugie, MG ma wbudowane wielopoziomowe i wszystkie wielopoziomowe metody DD zostały opracowane z teorią i implementacjami dwupoziomowymi. Ogranicza to przestrzeń zgrubnych przestrzeni siatki, których można użyć w MG - muszą być one rekurencyjne. Na przykład nie można zaimplementować FETI w środowisku MG. Ludzie stosują niektóre wielopoziomowe metody DD, jak wspomniał Jed, ale przynajmniej niektóre z obecnych popularnych metod DD nie wydają się być możliwe do zastosowania rekurencyjnie.

Po trzecie, postrzegam same algorytmy jako praktykowane jako bardzo różne. Mówiąc jakościowo powiedziałbym, że metody DD rzutują na granice domen i rozwiązują ten problem interfejsu. MG działa bezpośrednio z natywnymi równaniami. Uniknięcie tej projekcji pozwala łatwo zastosować MG do problemów nieliniowych i niesymetrycznych. Chociaż teoria prawie odchodzi z powodu nieliniowych i niesymetrycznych problemów, pracowali dla wielu ludzi. MG jednoznacznie rozdziela problem na dwie części: zgrubną przestrzeń siatki do skalowania i iteracyjny solver (gładszy) do rozwiązania fizyki. Ma to kluczowe znaczenie dla zrozumienia i pracy z MG i jest dla mnie atrakcyjną własnością.

Chociaż teoretycznie wygładzacze i zgrubne przestrzenie siatki są ściśle ze sobą powiązane, w praktyce często można zamieniać różne wygładzania i wyłączać jako parametr optymalizacji. Jak wspomniano Jed, wygładzacze punktowe lub wierzchołkowe są popularne i zwykle szybsze, ale w przypadku trudnych problemów przydatne mogą być cięższe wygładzacze. Ten wykres pochodzi z mojej pracy doktorskiej pokazującej czas rozwiązania jako funkcję współczynnika Poissona dla Jacobiego, bloku Jacobiego i „dodatku Schwarz” (częściowo zachodzących na siebie). Jest trochę trudny do odczytania, ale przy najwyższym współczynniku Poissona (0,499) nakładający się Schwarz jest około 2x szybszy niż (wierzchołek) Jocobi, podczas gdy jest około 3x wolniejszy przy wskaźnikach Poissona dla pieszych.

Zgodnie z odpowiedzią Jeda MG używa umiarkowanego zgrubienia, podczas gdy DD używa szybkiego zgrubienia. Myślę, że robi to różnicę, gdy są one równoległe. Będzie wiele komunikacji i synchronizacji dla MG, aby przejść przez wiele poziomów zgrubienia, które są równoważne pojedynczemu zgrubieniu DD. Kolejnym punktem odpowiedzi Jeda jest to, że MG używa taniej wygładzacza, a DD używa silnej wygładzarki. Biorąc pod uwagę te dwa punkty, doniesiono, że MG na grubszych poziomach będzie miał złe wskaźniki komunikacji / obliczeń. Zgodnie z prawem Amdahla równoległe przyspieszenie nie jest dobre. Rozwiązaniem tego problemu jest równoległa korekcja gruboziarnistych siatek, taka jak kondycjoner BPX. Poza tym MG może używać DD tak płynniej, jak wskazał Adams, a MG można również używać w poddomenach DD. W oparciu o rozważania, które wskazał Barker, wydaje mi się, że lepsze jest używanie MG w DD, które wykorzystuje zarówno równoległe DD, jak i optymalną złożoność MG.

Chciałbym dodać jeden drobny dodatek do doskonałej odpowiedzi Jeda, a mianowicie, że motywacje obu podejść są (a przynajmniej były) różne.

Rozkład domen jest motywowany jako technika obliczeń równoległych. Zwłaszcza w przypadku metod jednopoziomowych implementację DD na maszynie równoległej jest bardzo naturalne - dzielisz domenę na części i oddajesz każdą sztukę innemu procesorowi. W pewnym sensie motywacją stojącą za DD jest podział operacji arytmetycznych między procesorami.

Istnieją dobre implementacje wielu równoległych sieci, ale często jest to mniej naturalne wykonywanie równolegle. Zamiast tego motywacją stojącą za multigridem jest przede wszystkim wykonywanie mniej operacji arytmetycznych.

$H$$h$$\mathcal{O}(\frac{1}{Hh})$

$h$$H$