Können wir bei einem tridiagonalen linearen SPD-System vorberechnen, dass drei beliebige Indizes in O (1) -Zeit verknüpft werden können?

Betrachten Sie ein symmetrisches positives definitives tridiagonales lineares System wobei und . Wenn wir bei drei Indizes nur Gleichungszeilen annehmen, die streng zwischen und gelten, können wir Zwischenvariablen eliminieren, um eine Gleichung der Form

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$ wo

. Diese Gleichung bezieht den Wert von

auf

unabhängig vom "äußeren" Einfluss (z. B. wenn eine Einschränkung eingeführt wurde, die

beeinflusst ).

v > 0

$v > 0$

x_{j}

$x_j$

x_{i}, x_{k}

$x_i,x_k$

x_{0}

$x_0$

Frage : Ist es möglich, das lineare System in -Zeit vorzuverarbeiten, so dass die Verknüpfungsgleichung für jede in -Zeit bestimmt werden kann? $Ax = b$ $O(n)$ $(i,j,k)$ $O(1)$

Wenn die Diagonale von 2 ist, sind die offdiagonals , und , das gewünschte Ergebnis für die Poisson - Gleichung diskretisiert das analytische Ergebnis. Leider ist es nicht möglich, ein allgemeines tridiagonales SPD-System in eine Poisson-Gleichung mit konstantem Koeffizienten umzuwandeln, ohne die tridiagonale Struktur zu brechen, im Wesentlichen, weil verschiedene Variablen unterschiedliche Niveaus des "Screenings" aufweisen können (lokal strenge positive Bestimmtheit). Eine einfache diagonale Skalierung von kann beispielsweise die Hälfte der DOFs von eliminieren , nicht jedoch die andere Hälfte. $A$ $-1$ $b = 0$ $x$ $2n-1$ $A$

Intuitiv würde eine Lösung für dieses Problem erfordern, das Problem so anzuordnen, dass die Menge des Screenings in einem linearen Größenarray akkumuliert und dann irgendwie "aufgehoben" werden könnte, um zu der Verknüpfungsgleichung für das gegebene Tripel zu gelangen.

Update (mehr Intuition) : In Bezug auf PDEs habe ich ein diskretisiertes lineares elliptisches Problem in 1D und möchte wissen, ob ich für die Vorberechnung ausgeben kann, um eine Art "analytische" Lösung zu erstellen, die nachgeschlagen werden kann in Zeit, wo ich variieren darf, wo die Randbedingungen sind. $O(n)$ $O(1)$

linear-algebra poisson Geoffrey Irving
quelle

Antworten:

Hier ist eine etwas instabile Lösung, die nur funktioniert, wenn die Kopplung zwischen Variablen immer nicht entartet ist. Nehmen Sie der Einfachheit halber an, dass . Zuerst precompute die Verknüpfung Gleichungen für für , sagen wir $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}$

Wenn nun , können wir die ten und ten Verknüpfungsgleichungen kombinieren und eliminieren , um zu erhalten $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}$

$x_0$ $(i,j,k)$ $b_j = 0$ $b_j = 0$

Geoffrey Irving
quelle

Nachdem ich dies implementiert habe, kann ich bestätigen, dass (1) es in exakter Arithmetik funktioniert und (2) es extrem instabil ist. Intuitiv führt diese Lösung eine Reihe von Extrapolationen von Exponentialfunktionen durch, wodurch der schöne interpolatorische Charakter elliptischer Probleme gebrochen wird.

Geoffrey Irving

b_{j} \approx 0

$b_j\approx 0$

n \log n

$n\log n$

O (n)

$O(n)$

O (\log n)

$O(\log n)$

Ich frage mich, ob Sie mit einer zyklischen Reduktionsfaktorisierung von A (von der ich glaube, dass sie immer noch O (n) ist) etwas Nützliches tun könnten, indem Sie so viele Blöcke wiederverwenden, die unverändert bleiben würden, wenn eine zusammenhängende Haupt-Submatrix von A berücksichtigt wird. Ich bezweifle es gibt dir O (1), aber vielleicht O (log n) ...

Robert Bridson
quelle

O (\log n)

$O(\log n)$

Keine Chance auf Amortisation?

Robert Bridson

Es gibt noch viele andere Abschreibungen, also ist das durchaus möglich. Ich weiß allerdings noch nicht wie.

Geoffrey Irving

Dies ist, was ich brauchen würde, um die Kosten zu amortisieren: cstheory.stackexchange.com/questions/18655/… .

Geoffrey Irving

Groß! Jemand hat eine wunderbare Lösung für diese theoretische Frage veröffentlicht, daher sollte ich die Antwort auf diese Frage nicht mehr brauchen. Die Halbgruppen-Multiplikationsoperation in dieser Frage eliminiert eine Zwischenvariable.

Geoffrey Irving

Hier ist ein weiterer Versuch, der stabiler als die Stornierungsmethode ist, aber immer noch nicht sehr gut.

$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), "Eine Übersicht über die Umkehrung von symmetrischen Diagonal- und Blocktridiagonalmatrizen".

Geoffrey Irving
quelle