Lösen

Ich habe Matrizen $A$ $G$ $A$ $n\times n$ $n$ $G$ $n\times m$ $m$ $1 \lt m \lt 1000$ $1$ $0$ $G^TG = I$ $A$ $Ax = b$ $\mathrm{BiCGStab}(l)$ $A^{-1}$

Ich möchte ein System der Form lösen: $(G^TA^{-1}G)x = b$ $x$ $b$ $m$ $A^{-1}$

linear-algebra linear-solver sparse-matrix krylov-method Costis
quelle

Ich habe meiner Antwort gerade eine Bemerkung zur Ausnutzung der 0-1-Struktur hinzugefügt.

Arnold Neumaier

Antworten:

Den Vektor einführen $y:=-A^{-1}Gx$ und lösen das große gekoppelte System $Ay+Gx=0$ , $G^Ty=-b$ zum $(y,x)$ gleichzeitig mit einer iterativen Methode. Ob $A$ ist symmetrisch (wie es wahrscheinlich scheint, obwohl Sie es nicht explizit angeben), dann ist das System symmetrisch (aber unbestimmt, obwohl quasidefinit, wenn $A$ Dies kann Ihnen bei der Auswahl einer geeigneten Methode helfen. (relevante Schlüsselwörter: KKT-Matrix, quasidefinite Matrix).

Bearbeiten: Als $A$ ist komplex symmetrisch, ebenso wie die erweiterte Matrix, aber es gibt keine Quasidefinitität. Sie können jedoch die $Ax$ Routine zu berechnen $A^*x=\overline{A\overline x}$ ; Aus diesem Grund können Sie eine Methode wie QMR ftp://ftp.math.ucla.edu/pub/camreport/cam92-19.pdf (für reale Systeme konzipiert) anpassen. Sie können sie jedoch problemlos für komplexe Systeme mit dem Zusatz in umschreiben Ort der Transponierung), um Ihr Problem zu lösen.

Edit2: Eigentlich ist die (0,1) -Struktur von $G$ bedeutet, dass Sie beseitigen können $x$ und die Komponenten von $G^Ty$ symbolisch, so dass am Ende ein kleineres System zu lösen ist. Das bedeutet, sich mit der Struktur von zu beschäftigen $A$ und zahlt nur wenn $A$ wird explizit in spärlichem Format angegeben und nicht als linearer Operator.

Arnold Neumaier
quelle

Vielen Dank! A ist komplex symmetrisch. Gibt es Grund zu der Annahme, dass der Zustand der Augmented Matrix schlechter ist als der der Originalmatrix?

A

$A$ ? Wenn m klein ist, ist die erweiterte Matrix nur unwesentlich größer als A, daher würde ich vermuten, dass die iterative Lösung dieses erweiterten Systems nicht viel schwieriger sein sollte als die Lösung eines Systems mit A?

Costis

Die Zustandsnummer der beiden Systeme hängt im Allgemeinen nicht zusammen. es kommt sehr darauf an was

G

$G$ ist. - Ich habe meiner Antwort Informationen hinzugefügt, wie man komplexe Symmetrie ausnutzt.

Arnold Neumaier

Hallo Leute! Danke für all die Antworten; Dieser Ort ist großartig! Eine Erweiterung der ursprünglichen Frage: Nehmen wir jetzt an, dass ich habe

(G^{T} A^{- H} B A^{- 1} G) x = b

$(G^TA^{-H}BA^{-1}G)x=b$ , wobei G und A die gleiche Bedeutung wie in der ursprünglichen Frage haben, B jedoch eine rangdefiziente nxn-Matrix (gleiche Größe wie A) und das Ganze ist

G^{T} A^{- H} B A^{- 1} G

$G^TA^{-H}BA^{-1}G$ ist voller Rang. Wie würden Sie vorgehen, um das neue System zu lösen, da jetzt das Inverse von B nicht existiert und Sie es nicht haben können?

A B^{- 1} A^{H}

$AB^{-1}A^H$ . Ich denke nicht, dass es einfach mit der Pseudoinverse von B funktionieren würde.

Costis

Vorstellen

y := A^{- 1} G x

$y:=A^{-1}Gx$ und

z := A^{- H} B y

$z:=A^{-H}By$ und verfahren analog zum erarbeiteten Fall. (Möglicherweise müssen Sie auch berücksichtigen

B

$B$ in Matrizen mit vollem Rang und führe einen zusätzlichen Zwischenvektor ein.)

Arnold Neumaier

Hallo Arnold. Danke, das funktioniert wirklich! Ich habe es mit einigen sehr kleinen Testbeispielen getestet und es funktioniert großartig. Mein iterativer Löser hat jedoch große Probleme beim Invertieren der erweiterten Matrix. Während es nur ungefähr 80 Iterationen (ein paar Sekunden) dauert, um ein System der Form zu lösen

A x = b

$Ax=b$ Bei der ursprünglichen A-Matrix benötigt das System mit der erweiterten Matrix (2n + mx 2n + m oder 2n-mx 2n-m unter Verwendung des @ wolfgang-bangerth-Ansatzes) über zehntausende von Iterationen (mehrere Stunden), um gelöst zu werden für eine RHS. Gibt es Strategien zur Beschleunigung der Konvergenz? vielleicht ein Vorkonditionierer?

Costis

Nach Arnolds Antwort können Sie etwas tun, um das Problem zu vereinfachen. Schreiben Sie das System insbesondere neu als $Ay+Gx=0, G^Ty=-b$ . Dann notiere das aus der Aussage, dass $G$ ist groß und schmal und jede Zeile hat nur eine 1 und ansonsten Nullen, dann die Anweisung $G^Ty=-b$ bedeutet, dass eine Teilmenge der Elemente von $y$ einen festen Wert haben, nämlich die Elemente von $-b$ .

Sagen wir das der Einfachheit halber so $G$ hat $m$ Spalten und $n$ Reihen und das genau das erste $m$ Zeilen enthalten solche, die die Elemente von neu ordnen $x$ Ich kann es so machen $G$ hat die $m \times m$ Identitätsmatrix oben und a $n-m \times m$ Nullmatrix unten. Dann kann ich partitionieren $y=(y_c,y_f)$ in $m$ "eingeschränkt" und $n-m$ "freie" Elemente damit $y_c=-b$ . Ich kann auch partitionieren $A$ damit $A=\begin{pmatrix} A_{cc} & A_{cf} \\ A_{fc} & A_{ff} \end{pmatrix}$ . Aus der Gleichung $Ay+Gx=0$ Ich bekomme dann folgendes:

{EIN}_{c c} y_{c} + {EIN}_{c f} y_{f} + x = 0, {EIN}_{f c} y_{c} + {EIN}_{f f} y_{f} = 0

$A_{cc} y_c + A_{cf} y_f + x = 0, \\ A_{fc} y_c + A_{ff} y_f = 0$ und mit dem, was wir wissen

y_{c}

$y_c$ wir haben aus der zweiten dieser Gleichungen

{EIN}_{f f} y_{f} = {EIN}_{f c} b

$A_{ff} y_f = A_{fc} b$ und folglich

x = {EIN}_{c c} b - {EIN}_{c f} {EIN}_{f f}^{- 1} {EIN}_{f c} b .

$x = A_{cc} b - A_{cf} A_{ff}^{-1} A_{fc} b.$ Mit anderen Worten, die einzige Matrix, die Sie invertieren müssen, ist die Teilmenge von

A

$A$ deren Zeilen und Spalten werden in nicht erwähnt

G

$G$ (der Nullraum von

G

$G$ ). Dies können Sie leicht tun: (i) berechnen

z = A_{f c} b

$z=A_{fc} b$ ; (ii) Verwenden Sie den Löser, den Sie lösen müssen

A_{f f} h = z

$A_{ff} h = z$ ; (iii) berechnen

x = A_{c c} b - A_{c f} h

$x = A_{cc} b - A_{cf} h$ .

Mit anderen Worten, angesichts der Struktur von $G$ ist das Lösen des linearen Systems, das Sie haben, wirklich nicht schwieriger als das Lösen eines einzelnen linearen Systems mit $A$ .

Wolfgang Bangerth
quelle

Aber wir wissen es $G$ , $G^T$ und $A$ , so

$G^T A^{-1} G x = b$

$G G^T A^{-1} G x = G b$

Schon seit $G^T G = I$ , dann $G^T = G^{-1}$ , so $G G^T=I$ :

$A^{-1} G x = G b$

$A A^{-1} G x = A G b$

$G x = A G b$

$G^T G x = G^T A G b$

$x = G^T A G b$

Solange ich nichts verpasst habe, brauchen Sie keine Iteration oder keinen Löser, um das gegebene x zu berechnen $G$ , $A$ und $b$ .

Phil H
quelle

G^{T}

$G^T$ eine linke Umkehrung von

G

$G$ bedeutet nicht, dass es auch eine Rechtsumkehrung ist. Erwägen

G = e_{1}

$G=e_1$ , woher

G^{T} = e_{1}^{T}

$G^T=e_1^T$ ist eine Linksumkehrung, aber

G G^{T} = e_{1} e_{1}^{T} \neq I

$GG^T=e_1e_1^T\neq I$ .

Jack Poulson

G \in C^{n} \otimes C^{m}

$G\in \mathbb{C}^n\otimes \mathbb{C}^m$ daher

G^{T} G = I_{m \times m}

$G^TG=I_{m\times m}$ , aber

G G^{T} \neq I_{n \times n}

$GG^T\ne I_{n\times n}$ . Es ist eher ein Projektor auf einem Unterraum.

Deathbreath