Jak zrównoleglić metodę wielosiatkową do rozwiązywania liniowego układu równań?

11

Jak rozumiem, metoda wielosiatkowa rozwiązuje układ liniowy, rozwiązując zgrubną wersję tego samego problemu (tam przez wyeliminowanie błędu niskiej częstotliwości), a następnie rzutując z powrotem na drobną siatkę, aby wygładzić błędy wysokiej częstotliwości. W przypadku dużych systemów widzę, jak można iterować metodę równoległą na każdym poziomie siatki. Czy to podejście jest skalowane równolegle? Czy istnieje inne źródło współbieżności w algorytmie, które można wykorzystać równolegle?

Paweł
źródło

Odpowiedzi:

14

Równoległe geometryczne wielosieciowe jest łatwe do wdrożenia na siatkach strukturalnych. Algebraiczne i nieustrukturyzowane wielosieciowe są bardziej techniczne, zobacz tę odpowiedź, aby uzyskać linki do implementacji.

VlogcNNc2d3ddlog2logcN. Nie widziałem jeszcze demonstracji na prawdziwym sprzęcie, w której zwiększona współbieżność uzasadnia gorsze stałe i zmniejszoną niezawodność metod addytywnych.

O(N/P)

W praktyce grube siatki szybko osiągają silny limit skalowalności (powyżej którego dodanie większej liczby procesów zwiększa czas działania), dlatego powinny znajdować się na coraz mniejszych komunikatorach MPI. Dodaje to niewielką złożoność wdrożenia. W przypadku problemów, w których poziomy zgrubne mają zbyt dużą strukturę, aby kontynuować zgrubienie, rozwiązanie problemu zgrubnego może stać się wąskim gardłem.

Do testowania różnych równoległych metod wielosieciowych zalecam użycie biblioteki takiej jak PETSc, która pozwala na uruchamianie wielu różnych algorytmów przy bardzo małym kodzie użytkownika.

Jed Brown
źródło
Link Adamsa (2001) już nie działa. Uważam, że miałeś na myśli ten artykuł: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1592790&tag=1 . „Nieustrukturyzowany algorytm Gaussa-Seidela dla rozproszonej pamięci dla wygładzaczy wieloskładnikowych” Daj mi znać, jeśli się mylę.
nukeguy