Rozważmy symetryczny dodatnio określona tridiagonal system liniowy , gdzie i . Biorąc pod uwagę trzy wskaźniki , jeśli przyjmiemy tylko rzędy równań ściśle między i hold, możemy wyeliminować zmienne pośrednie, aby uzyskać równanie w postaci gdzie . To równanie odnosi wartość do niezależnie od wpływu „zewnętrznego” (powiedzmy, jeśli wprowadzono ograniczenie wpływające na ).A ∈ R n × n b ∈ R n 0 ≤ i < j < k < n i k u x i + v x j + w v > 0 x j x i , x k x 0
Pytanie : Jest to możliwe do przetwarzania wstępnego układu liniowego w czasie, tak, że łącząca równanie dla każdego można określić w razem?O ( n ) ( i , j , k ) O ( 1 )
Jeśli przekątna wynosi 2, nierównomierne wartości wynoszą , a , pożądanym wynikiem jest wynik analityczny dla dyskretnego równania Poissona. Niestety, nie jest możliwe przekształcenie ogólnego układu tridiagonalnego SPD w równanie Poissona o stałym współczynniku bez zerwania struktury tridiagonalnej, zasadniczo dlatego, że różne zmienne mogą mieć różne poziomy „przesiewania” (ściśle ścisła lokalnie dodatnia). Na przykład proste skalowanie po przekątnej może wyeliminować połowę DOF z ale nie drugą połowę.- 1 b = 0 x 2 n - 1 A.
Intuicyjnie rozwiązanie tego problemu wymagałoby takiego uporządkowania problemu, aby ilość przesiewania mogła zostać zgromadzona w tablicy rozmiarów liniowych, a następnie w jakiś sposób „anulowana”, aby uzyskać równanie łączące dla danej potrójnej.
Aktualizacja (więcej intuicji) : Jeśli chodzi o PDE, mam dyskretny liniowy problem eliptyczny w 1D i chcę wiedzieć, czy mogę wydać na wstępne obliczenia, aby stworzyć jakieś „analityczne” rozwiązanie, które można sprawdzić w czasie , gdzie wolno mi zmieniać, gdzie są warunki brzegowe.O ( 1 )
źródło
Zastanawiam się, czy mógłbyś zrobić coś użytecznego z cyklicznym zmniejszaniem faktoryzacji A (który, jak sądzę, wciąż ma rozmiar O (n)), ponownie wykorzystując tyle bloków, które pozostałyby niezmienione, biorąc pod uwagę ciągłą główną podmacierz A. daje ci O (1), ale może O (log n) ...
źródło
Oto kolejna próba, która jest bardziej stabilna niż metoda anulowania, ale wciąż niezbyt dobra.
[1]: Gerard Meurant (1992), „Recenzja odwrotności symetrycznych macierzy diagonalnych i blokowych tridiagonalnych”.
źródło