Czy mając trójridiagonalny układ liniowy SPD, możemy wstępnie obliczyć, aby dowolne trzy wskaźniki można było połączyć w czasie O (1)?

11

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

Ax=b
ARn×nbRn0i<j<k<nik
uxi+vxj+wxk=c
v>0xjxi,xkx0

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 )Ax=bO(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.A1b=0x2n1A

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 )O(n)O(1)

Geoffrey Irving
źródło

Odpowiedzi:

2

Oto nieco niestabilne rozwiązanie, które działa tylko wtedy, gdy sprzężenie między zmiennymi jest zawsze nie generowane. Załóżmy dla uproszczenia, że . Najpierw obliczyć równań łączących dla dla , powiedzmyn ( 0 , i , n - 1 ) 0 i < nb=0n(0,i,n1)0i<n

xi=aix0+bixn1

Teraz, biorąc pod uwagę , możemy połączyć te i te równania łączące i wyeliminować aby uzyskaći j x n - 1i<jijxn1

bjxi=aibjx0+bibjxn1bixj=ajbix0+bibjxn1bjxibixj=(aibjajbi)x0xi=aibjajbibjx0+bibjxj

Proces ten można powtórzyć jeszcze raz, aby wyeliminować podane . Niestety tracimy stabilność w pobliżu lub ogólnie, jeśli układ trójosiowy rozdzieli się na niezależne bloki. Jeśli nie stanowi to problemu, ale martwię się o podział na małe, ale dodatnie wartości. ( i , j , k ) b j = 0 b j = 0x0(i,j,k)bj=0bj=0

Geoffrey Irving
źródło
Po wdrożeniu tego, mogę potwierdzić, że (1) działa dokładnie arytmetycznie i (2) jest wyjątkowo niestabilny. Intuicyjnie to rozwiązanie wykonuje szereg ekstrapolacji funkcji wykładniczych, co psuje ładny interpolacyjny charakter problemów eliptycznych.
Geoffrey Irving,
Wygląda na to, że twoje podejście polega na wstępnym obliczeniu czegoś takiego jak funkcja Zielonego dla wszystkich wewnętrznych wskaźników. Nic więc dziwnego, że będziesz miał kłopoty, gdy , ponieważ informacje o wartościach granicznych z trudem rozprzestrzeniają się do interesującego miejsca. Nie sądzę, by istniałby ogólny sposób na obejście tego. Wydaje się, że może być lepiej czyni strukturę drzewa (być może jest to precomputing wysiłek), który pozwala uzyskać funkcję Greena dla podrozdziałach domeny na ominięcie potencjalnych punktów zapalnych. n log nbj0nlogn
Victor Liu
Wersja drzewa to obliczenie wstępne plus na potrójny. Niestety szukam konkretnie rozwiązań czasu liniowego. O ( log n )O(n)O(logn)
Geoffrey Irving
2

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

Robert Bridson
źródło
O(logn)
Nie masz szans na amortyzację?
Robert Bridson
Trwa wiele innych spłat, więc jest to całkiem możliwe. Jednak nie wiem jeszcze jak.
Geoffrey Irving
Właśnie tego potrzebowałbym w celu amortyzacji kosztów: cstheory.stackexchange.com/questions/18655/… .
Geoffrey Irving
Świetny! Ktoś opublikował wspaniałe rozwiązanie tego pytania, więc nie powinienem już potrzebować odpowiedzi na to pytanie. Operacja mnożenia półgrup w tym pytaniu eliminuje zmienną pośrednią.
Geoffrey Irving,
1

Oto kolejna próba, która jest bardziej stabilna niż metoda anulowania, ale wciąż niezbyt dobra.

AB=A1

Bij=bi+1bjdj+1dnδiδn

ijbidi,δiULLUAi<j<k

xj=(BjiBki)T(BiiBikBkiBkk)1(xixk)

ikik2×2

[1]: Gerard Meurant (1992), „Recenzja odwrotności symetrycznych macierzy diagonalnych i blokowych tridiagonalnych”.

Geoffrey Irving
źródło