Czy algorytm Thomasa jest najszybszym sposobem rozwiązania symetrycznego, ukośnego, rzadkiego, tridiagonalnego układu liniowego

Zastanawiam się, czy algorytm Thomasa jest najszybszym (możliwym do udowodnienia?) Rozwiązaniem symetrycznego, dominującego po przekątnej, rzadkiego systemu tridiagonalnego pod względem złożoności algorytmicznej (nie szukając pakietów implementacyjnych takich jak LAPACK itp.). Wiem, że zarówno algorytm Thomasa, jak i multigrid mają złożoność , ale może stały współczynnik dla multigrid jest mniejszy? Nie wydaje mi się, żeby multigrid mógł być szybszy, ale nie jestem pozytywny. $O(n)$

Uwaga: Rozważam przypadek, w którym matryce są bardzo duże. Dopuszczalne są metody bezpośrednie lub iteracyjne.

— James
źródło

Odpowiedzi:

$8N$

$O(N)$

— Aureliusz
źródło

Dzięki. Zdaję sobie sprawę, że metody iteracyjne nie są dokładne. Powinienem był określić bardzo małą tolerancję (powiedzmy 10 ^ -15) i traktowałem to jako „dokładne” dla celów porównawczych.

— James

@ user2697246 cóż, zapytałeś o „możliwe do udowodnienia” najszybciej. Dokładny współczynnik zbieżności dla wielosieciowego (lub dowolnego schematu iteracyjnego) zawsze będzie zależeć od samego rozwiązania i początkowej domysły - rozwiązanie liniowe zostanie skutecznie rozwiązane dokładnie w jednym kroku, podczas gdy coś bardziej oscylacyjnego zajmie więcej operacji. Thomas ma dokładną, stałą liczbę operacji dla wszystkich przypadków. Praktycznie rzecz biorąc, nigdy nie pokonasz Thomasa za (szeregowe) rozwiązanie układu trójosiowego w przypadku nietrywialnym.

— Aurelius

@Aurelius Czy algorytm Thomasa może być zrównoleglony? Jeśli nie, jest to jedna z głównych zalet multigrid!

— Nick Alger

O (N l o g N)

$O(N log N)$

N

$N$

Jedna korekta, algorytm Thomasa wymaga operacji 8N, a nie 9N. Co rozumiesz przez „wielosiatkowe ... posiadające rozwiązanie liniowe”? Wszystkie rozważane tutaj systemy są liniowe.

— Doug Lipinski

Krótka odpowiedź jest taka, że algorytm Thomasa będzie szybszy niż jakikolwiek schemat iteracyjny dla prawie wszystkich przypadków. Wyjątkiem może być zastosowanie pojedynczej iteracji bardzo prostego schematu iteracyjnego, takiego jak Gauss-Seidel, ale jest mało prawdopodobne, aby dało to akceptowalne rozwiązanie. Pomija to również obawy związane z przetwarzaniem równoległym.

$\mathcal O(n)$ $\mathcal O(n)$

$5N$ $3N$ $3N-2$ $2N-2$

— Doug Lipiński
źródło

„Wielosieciowy jest szczególnie złym wyborem w przypadku macierzy trój przekątnej, ponieważ chociaż wielosiatkowym jest O (n), stała jest dość duża”. Też tak myślę, ale Google ogłosił wiersz w książce Trottenburga Multigrid, twierdząc, że stała 0,1-0,2, podana bez dowodu. Nie sądzę, że w to wierzę.

— Aurelius

@Aurelius Interesujące. Jest to oczywiście niemożliwe w ogólnym przypadku, ponieważ w macierzy trójosiowej są 3 wpisy. Jeśli koszt wynosi ~ 0,1 * N, oznacza to, że nigdy nie operujesz większością wpisów.

— Doug Lipiński

Tak, jesteśmy na tej samej stronie; sama ocena szablonu 3-punktowego wymaga operacji 3N. Właśnie przeszukiwałem, więc może całkowicie błędnie zinterpretowałem to oświadczenie, ale możesz to zobaczyć na własne oczy w wyciągu z książek Google.

— Aurelius

Pełny cytat (str. 21) brzmi: „Efektywność w sensie praktycznym oznacza, że stałe proporcjonalności w tym stwierdzeniu O (N) są małe lub umiarkowane. Tak jest w przypadku wielosieciowego: jeśli dobrze zaprojektowane, czynniki konwergencji niezależne od h mogą być bardzo małe (w zakresie 0,1-0,2 lub nawet mniejszym), a liczba operacji na nieznany na krok iteracji jest również niewielka. ” 0,1-0,2 odnosi się do resztkowej redukcji dla każdego cyklu wielosieciowego. Stała na O (N) byłaby rzędu 1,5-2,0-krotności macierzy pomnożonej na cykl (łącznie w sumie kilkanaście lub dwa cykle).

— Godric Seer

Ach, dzięki @GodricSeer, to ma większy sens.

— Aurelius

Pętle wielosiatkowe nawet na jednym rdzeniu są wektoryzowane przez optymalizator. Chociaż liczby operacji mogą pomóc, nie powinniśmy zapominać, że nawet w świecie szeregowym procesory mają równoległość wektorów, a zatem czas do rozwiązania może nie być dokładnie taki, jak przewidujemy na podstawie analizy kosztów.

— Hasbestein
źródło