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.

$8N$

$O(N)$

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$

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.