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

11

Betrachten Sie ein symmetrisches positives definitives tridiagonales lineares System wobei A R n × n und b R n sind . Wenn wir bei drei Indizes 0 i < j < k < n nur Gleichungszeilen annehmen, die streng zwischen i und k gelten, können wir Zwischenvariablen eliminieren, um eine Gleichung der Form u x i + v x j + w x k = zu erhalten c

Ax=b
ARn×nbRn0i<j<k<nik
uxi+vxj+wxk=c
wo . Diese Gleichung bezieht den Wert von x j auf x i , x k unabhängig vom "äußeren" Einfluss (z. B. wenn eine Einschränkung eingeführt wurde, die x 0 beeinflusst ).v>0xjxi,xkx0

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

Wenn die Diagonale von 2 ist, sind die offdiagonals - 1 , und b = 0 , 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 x kann beispielsweise die Hälfte der 2 n - 1 DOFs von A eliminieren , nicht jedoch die andere Hälfte.A1b=0x2n1A

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 O ( 1 ) Zeit, wo ich variieren darf, wo die Randbedingungen sind.O(n)O(1)

Geoffrey Irving
quelle

Antworten:

2

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 n Verknüpfung Gleichungen für ( 0 , i , n - 1 ) für 0 i < n , sagen wirb=0n(0,i,n1)0i<n

xi=aix0+bixn1

Wenn nun , können wir die i- ten und j- ten Verknüpfungsgleichungen kombinieren und x n - 1 eliminieren , um zu erhalteni<jijxn1

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

x0(i,j,k)bj=0bj=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
bj0nlogn
O(n)O(logn)
2

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(logn)
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
1

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

AB=A1

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

ijbidi,δiULLUAi<j<k

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

ikik2×2

[1]: Gerard Meurant (1992), "Eine Übersicht über die Umkehrung von symmetrischen Diagonal- und Blocktridiagonalmatrizen".

Geoffrey Irving
quelle