Jakich wskazówek należy przestrzegać przy wyborze rzadkiego solvera systemu liniowego?

49

W aplikacjach pojawiają się rzadkie systemy liniowe. Do rozwiązania tych systemów jest wiele procedur do wyboru. Na najwyższym poziomie istnieje przełom między metodami bezpośrednimi (np. Rzadka eliminacja Gaussa lub rozkład Choleskiego, ze specjalnymi algorytmami porządkowania i metodami wielopłaszczyznowymi) i iteracyjnymi (np. GMRES, gradient (sprzężony)).

Jak określić, czy zastosować metodę bezpośrednią, czy iteracyjną? Po dokonaniu wyboru, jak wybrać konkretny algorytm? Wiem już o wykorzystaniu symetrii (np. Użyj gradientu sprzężonego dla rzadkiego symetrycznego pozytywnego określonego systemu), ale czy są jakieś inne względy, które należy wziąć pod uwagę przy wyborze metody?

JM
źródło

Odpowiedzi:

33

Ważną rzeczą przy wyborze iteracyjnych solverów jest spektrum operatora, patrz ten artykuł . Jednak jest tak wiele negatywnych wyników, patrz ten artykuł, w którym żaden iteracyjny solver nie wygrywa dla wszystkich problemów, oraz ten dokument, w którym dowodzą, że mogą uzyskać dowolną krzywą zbieżności dla GMRES dla dowolnego spektrum. Dlatego wydaje się niemożliwe do przewidzenia zachowanie iteracyjnych solverów, z wyjątkiem kilku izolowanych przypadków. Dlatego najlepszym rozwiązaniem jest wypróbowanie ich wszystkich, przy użyciu systemu takiego jak PETSc , który również ma bezpośrednie solvery.

Matt Knepley
źródło
2
„Rzucaj w to wszystko, co możesz” było właściwie radą, do której byłem przyzwyczajony. :) Trzeci artykuł, do którego linkujesz, to coś, czego wcześniej nie widziałem; Dziękuję za to!
JM
2
Matt ma świetną odpowiedź, ale musisz wziąć ją w kontekście społeczności, z której pochodzi (informatyka naukowa na dużą skalę). Przekonasz się, że w przypadku małych problemów (powiedzmy, mniej niż sto tysięcy niewiadomych), bezpośrednie solwery znacznie przewyższają metody iteracyjne, jeśli problem nie jest silnie eliptyczny. W literaturze nie widziałem żadnych dobrych artykułów ogólnych, które poprowadziłyby cię w kierunku początkowej strategii początkowej, co jest dla mnie nieco zawstydzające.
Aron Ahmadia
5
Oszacowanie Arona jest dobre, ale silnie zależy od wypełnienia, ponieważ rzadkie bezpośrednie metody zwykle wyczerpują pamięć, zanim wyczerpią cierpliwość.
Matt Knepley
18

Wybór między metodami bezpośrednimi a iteracyjnymi zależy od celów i aktualnego problemu.

W przypadku metod Direct możemy zauważyć:

  • Macierzy współczynników liniowych zmian systemu na przebieg obliczania i mogą na wymagania dotyczące pamięci urządzenia rzadki spalinowe zwiększają nakładu pracy w wyniku wypełnienia w
  • Należy wypełnić, aby uzyskać przydatne wyniki
  • Faktoryzację można ponownie wykorzystać w kolejnych etapach, jeśli występuje wiele prawych stron
  • Może być stosowany tylko do rozwiązywania układów liniowych.
  • Rzadko zawodzi.

W przypadku metod iteracyjnych możemy zauważyć:

  • Celem jest częściowy wynik tylko po niewielkiej liczbie iteracji.
  • Wysiłek związany z rozwiązaniem powinien być mniejszy niż bezpośrednie metody dla tego samego problemu.
  • Ekonomiczny w odniesieniu do przechowywania (bez wypełniania)
  • Często łatwe do zaprogramowania.
  • Znane przybliżone rozwiązanie można wykorzystać.
  • Czasami są szybkie, a czasem nie (czasem nawet rozbieżne).
  • W przypadku złożonych problemów metody iteracyjne są znacznie mniej niezawodne w porównaniu do metod bezpośrednich.

Wskazówki, kiedy stosować metody bezpośrednie lub iteracyjne?

  • Metody iteracyjne, gdy macierz współczynników jest rzadka, a metody bezpośrednie nie mogą skutecznie wykorzystywać rzadkości (unikaj tworzenia wypełnień).
  • Metody bezpośrednie dla wielu prawej strony.
  • Metody iteracyjne mogą być bardziej wydajne, jeśli dokładność ma mniejsze znaczenie
  • Metody iteracyjne dla nieliniowych układów równań.
Allan P. Engsig-Karup
źródło
8
O(n)O(n)O(n2))O(1)
8

Całkowicie zgadzam się z odpowiedziami już udzielonymi. Chciałem dodać, że wszystkie metody iteracyjne wymagają pewnego wstępnego odgadnięcia. Jakość tej wstępnej domysły może często wpływać na współczynnik konwergencji wybranej metody. Metody takie jak Jacobi, Gauss Seidel i Successive Over Relaxation działają w celu iteracyjnego „wygładzenia” jak największej liczby błędów na każdym kroku ( szczegóły w tym dokumencie). Pierwsze kilka kroków dość szybko zmniejsza błąd wysokiej częstotliwości, ale błąd niskiej częstotliwości wymaga znacznie więcej itracji, aby go wygładzić. To powoduje, że konwergencja tych metod jest powolna. W takich przypadkach możemy przyspieszyć konwergencję, rozwiązując najpierw błąd niskiej częstotliwości (np. Rozwiązując ten sam problem na grubszej siatce), a następnie rozwiązując błąd wyższej częstotliwości (np. Na drobniejszej siatce). Jeśli zastosujemy tę koncepcję rekurencyjnie przez dzielenie i podbijanie, otrzymamy tak zwaną metodę Multi-grid. Nawet jeśli układ liniowy nie jest symetryczny, istnieją alternatywne implementacje metody wielosiatkowej dla dowolnego niesingularnego układu macierzy rzadkich (np. Algebraiczna metoda wielosiatkowa), które mogą przyspieszyć zbieżność rozwiązania. Ich skalowalność w systemach równoległych jest jednak przedmiotem wielu badań.

Paul
źródło
5
Ta odpowiedź wydaje się sprawiać wrażenie, że skuteczność multigrid wynika z trafnego wstępnego odgadnięcia. W rzeczywistości początkowe przypuszczenie jest niewielkim problemem dotyczącym problemów liniowych, a tak naprawdę dotyczy tylko Full Multigrid. Multigrid działa z powodu separacji spektralnej. Należy pamiętać, że sprawienie, by multigrid działał dobrze w przypadku trudnych problemów, jest znaczącym wyzwaniem. Multigrid działa całkiem dobrze równolegle, był kluczowym składnikiem wielu nagród Gordona Bella i kilka pakietów open source działa z wysoką wydajnością na największych dzisiejszych maszynach. W przypadku implementacji GPU spójrz na bibliotekę CUSP.
Jed Brown
W większości przypadków losowe wstępne zgadywanie jest wystarczające. W wyodrębnianiu wartości własnych za pomocą algorytmu Lanczos pomaga losowy wektor start / restart. Ponowne uruchamianie zdarza się czasami w algorytmie Lanczos.
AnilJ
3

W twoim pytaniu brakuje ważnej informacji: skąd pochodzi macierz. Struktura problemu, który próbujesz rozwiązać, ma duży potencjał do zasugerowania metody rozwiązania.

Jeśli macierz pochodzi z równania różniczkowego cząstkowego o gładkich współczynnikach, trudno będzie pokonać geometryczną metodę wielosiatkową, zwłaszcza w trzech wymiarach. Jeśli twój problem jest mniej regularny, dobrą metodą jest algebraiczna wielosieciowość. Oba zwykle łączy się z metodami Kryłowa-przestrzeni. Inne wydajne solwery można uzyskać z szybkich metod multipolowych lub szybkiej transformaty Fouriera.

Guido Kanschat
źródło