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

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?

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.

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

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

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.