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

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 x = b

$A x = b$

A \in R^{n \times n}

$A \in \mathbb{R}^{n \times n}$

b \in R^{n}

$b \in \mathbb{R}^n$

0 \leq i < j < k < n

$0 \le i < j < k < n$

i

$i$

k

$k$

u x_{i} + v x_{j} + w x_{k} = c

$u x_i + v x_j + w x_k = c$

v > 0

$v > 0$

x_{j}

$x_j$

x_{i}, x_{k}

$x_i,x_k$

x_{0}

$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? $Ax = b$ $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ę. $A$ $-1$ $b = 0$ $x$ $2n-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(n)$ $O(1)$

linear-algebra poisson

— Geoffrey Irving
źródło

Odpowiedzi:

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 , powiedzmy $b = 0$ $n$ $(0,i,n-1)$ $0 \le i < n$

x_{i} = a_{i} x_{0} + b_{i} x_{n - 1}

$x_i = a_i x_0 + b_i x_{n-1}$

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

\begin{aligned} b_{j} x_{i} & = a_{i} b_{j} x_{0} + b_{i} b_{j} x_{n - 1} \\ b_{i} x_{j} & = a_{j} b_{i} x_{0} + b_{i} b_{j} x_{n - 1} \\ b_{j} x_{i} - b_{i} x_{j} & = (a_{i} b_{j} - a_{j} b_{i}) x_{0} \\ x_{i} & = \frac{a_{i} b_{j} - a_{j} b_{i}}{b_{j}} x_{0} + \frac{b_{i}}{b_{j}} x_{j} \end{aligned}

$\begin{aligned} b_j x_i &= a_i b_j x_0 + b_i b_j x_{n-1} \\ b_i x_j &= a_j b_i x_0 + b_i b_j x_{n-1} \\ b_j x_i - b_i x_j &= (a_i b_j - a_j b_i) x_0 \\ x_i &= \frac{a_i b_j - a_j b_i}{b_j} x_0 + \frac{b_i}{b_j} x_j \end{aligned}$

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. $x_0$ $(i,j,k)$ $b_j = 0$ $b_j = 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.

b_{j} \approx 0

$b_j\approx 0$

n \log n

$n\log n$

— Victor Liu

Wersja drzewa to obliczenie wstępne plus na potrójny. Niestety szukam konkretnie rozwiązań czasu liniowego.

O (n)

$O(n)$

O (\log n)

$O(\log n)$

— Geoffrey Irving

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 (\log n)

$O(\log n)$

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,

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

$A$ $B = A^{-1}$

B_{i j} = b_{i + 1} \dots b_{j} \frac{d_{j + 1} \dots d_{n}}{δ_{i} \dots δ_{n}}

$B_{ij} = b_{i+1}\cdots b_j \frac{d_{j+1}\cdots d_n}{\delta_i \cdots \delta_n}$

$i \le j$ $b_i$ $d_i,\delta_i$ $UL$ $LU$ $A$ $i < j < k$

x_{j} = {(\begin{matrix} B_{j i} \\ B_{k i} \end{matrix})}^{T} {(\begin{array}{cc} B_{i i} & B_{i k} \\ B_{k i} & B_{k k} \end{array})}^{- 1} (\begin{matrix} x_{i} \\ x_{k} \end{matrix})

$x_j = \left(\begin{array}{c}B_{ji} \\ B_{ki}\end{array}\right)^T \left(\begin{array}{cc}B_{ii} & B_{ik} \\ B_{ki} & B_{kk}\end{array}\right)^{-1} \left(\begin{array}{c}x_i \\ x_k\end{array}\right)$

$i$ $k$ $i$ $k$ $2 \times 2$

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

— Geoffrey Irving
źródło