Lösen eines Systems mit einem kleinen Rangdiagonal-Update

9

Angenommen, ich habe das ursprüngliche große, spärliche lineare System: . Nun, ich habe nicht A - 1 als ein zu groß , um Faktor oder jede Art von Zersetzung ist A , aber davon ausgehen , dass ich habe die Lösung x 0 mit einem gefunden iterativen lösen.Ax0=b0A1Ax0

Jetzt möchte ich eine kleine Rangaktualisierung auf die Diagonale von A anwenden (einige der diagonalen Einträge ändern): wobei D eine Diagonalmatrix ist, auf deren Diagonale meistens Nullen und einige wenige liegen Werte ungleich Null. Wenn ich A - 1 hätte, könnte ich die Woodbury-Formel nutzen, um ein Update auf die Inverse anzuwenden. Ich habe dies jedoch nicht zur Verfügung. Kann ich irgendetwas tun, ohne das gesamte System erneut aufzulösen? Gibt es vielleicht eine Möglichkeit, einen Vorkonditionierer M zu finden, der leicht zu invertieren ist, so dass M A 1(A+D)x1=b0DA1M , so dass alles, was ich tun müsste, wenn ich x 0 habe , M - 1 anwendenwürde und eine iterative Methode in ein paar / wenigen Iterationen konvergieren würde?MA1A0x0M1

Costis
quelle
Beginnen Sie mit einem guten Vorkonditionierer für und möchten wissen, wie Sie ihn aktualisieren können? Welchen Rang hat das Update? (Ein Update mit Rang 1000 ist "klein" im Vergleich zu einer Matrix der Größe 10 9, aber nicht klein in Bezug auf die Anzahl der Iterationen.)A1000109
Jed Brown
hat eine Größe von 10 6 bis 10 7 und das Update umfasst <1000 (wahrscheinlich <100) Elemente. Ich verwende einen diagonalen Vorkonditionierer für A, der sehr gut funktioniert. Eine Aktualisierung wäre also trivial, aber ich habe mich gefragt, ob ich etwas Besseres tun kann, als das neue System von Grund auf neu aufzulösen. A106107
Costis
2
Die Lösung eines Systems sagt nicht viel darüber aus. Wenn Sie dasselbe System mehrmals lösen, erhalten Sie anhand der inversen Karte dieser Vektoren (und / oder der zugehörigen Krylov-Räume) einige Informationen, mit denen Sie die Konvergenz beschleunigen können. Wie viele Systeme lösen Sie jeweils?
Jed Brown
Derzeit bin ich die Lösung nur für einen RHS ( - Vektor) mit jeder A - Matrix vor der Modifikation A . bAA
Costis

Antworten:

4
  1. Speichern Sie in den Spalten zweier Matrizen und C alle Vektoren b j, auf die Sie die Matrix in den vorherigen Iterationen angewendet haben, und die Ergebnisse c j = A b j .BCbjcj=Abj

  2. Lösen Sie für jedes neue System (oder A x = b ' , was der Sonderfall D = 0 ist ) ungefähr das überbestimmte lineare System ( C + D B ) y b ' , z durch Auswahl einer Teilmenge der Zeilen (möglicherweise aller) und Verwendung einer Methode mit dichten kleinsten Quadraten. Beachten Sie, dass nur der ausgewählte Teil von C + D B zusammengebaut werden muss. Das ist also eine schnelle Operation!(A+D)x=bAx=bD=0(C+DB)ybC+DB

  3. Setze . Dies ist eine gute anfängliche Näherung, mit der die Iteration zum Lösen von ( A + D ) x ' = b ' gestartet werden kann . Falls weitere Systeme verarbeitet werden müssen, verwenden Sie die Matrixvektorprodukte in dieser neuen Iteration, um die Matrizen B und C auf dem resultierenden Subsystem zu erweitern.x0=By(A+D)x=bBC

Wenn die Matrizen und C nicht in den Hauptspeicher passen, speichern Sie B auf der Festplatte und wählen Sie die Teilmenge der Zeilen im Voraus aus. Auf diese Weise können Sie den relevanten Teil von B und C im Kern behalten, der zur Bildung des Systems der kleinsten Quadrate erforderlich ist, und das nächste x 0 kann durch einen Durchgang durch B berechnet werden, ohne dass der Kernspeicher verwendet wird.BCBBCx0B

Die Zeilen sollten so ausgewählt werden, dass sie ungefähr einer groben Diskretisierung des gesamten Problems entsprechen. Es sollte ausreichen, fünfmal mehr Zeilen als die Gesamtzahl der erwarteten Matrixvektormultiplikationen zu verwenden.

Edit: Warum funktioniert das? Konstruktionsbedingt sind die Matrizen und C durch C = A B verbunden . Wenn der Unterraum durch die Spalten der aufgespannten B die exakte Lösung Vektor enthält x ' (eine seltene , aber einfache Situation) , dann x ' hat die Form x ' = B y für einige y . Einsetzen dieser in die Gleichung, die x ' definiert , ergibt die Gleichung ( C + D B ) y = b 'BCC=ABBxxx=Byyx(C+DB)y=b. In diesem Fall ergibt der obige Prozess als Ausgangspunkt , was die genaue Lösung ist.x0=By=x

Im Allgemeinen kann man nicht erwarten , dass im Spaltenraum von B liegt , aber der erzeugte Startpunkt ist der Punkt in diesem Spaltenraum, der x ' am nächsten liegt , in einer Metrik, die durch die ausgewählten Zeilen bestimmt wird. Daher ist es wahrscheinlich eine sinnvolle Annäherung. Wenn mehr Systeme verarbeitet werden, wächst der Spaltenraum und die Annäherung wird sich wahrscheinlich stark verbessern, so dass man hoffen kann, in immer weniger Iterationen zu konvergieren.xB.x'

Edit2: Über den erzeugten Unterraum: Wenn man jedes System mit einer Krylov-Methode löst, überspannen die Vektoren, die verwendet werden, um den Startpunkt für das zweite System zu erhalten, den Krylov-Unterraum der ersten rechten Seite. Somit erhält man eine gute Annäherung, wenn dieser Krylov-Unterraum einen Vektor enthält, der nahe an der Lösung Ihres zweiten Systems liegt. Im Allgemeinen überspannen die Vektoren, die verwendet werden, um den Startpunkt für das -ste System zu erhalten, einen Raum, der den Krylov-Unterraum der ersten k rechten Seiten enthält.(k+1)k

Arnold Neumaier
quelle
Vielen Dank, Prof. Neumaier. Ich werde das ausprobieren. Könnten Sie mir vielleicht eine kurze Erklärung geben, wie das funktioniert?
Costis
Was ist auch, wenn ich dasselbe System für viele verschiedene RHS-Vektoren lösen möchte? dh , A x 1 = b 1 , A x 2 = b 2 usw. Gibt es Informationen, die ich aus den vorherigen Lösungen verwenden kann, um die nachfolgenden zu beschleunigen? EINx0=b0EINx1=b1EINx2=b2
Costis
@Costis: Eine Lösung mit derselben Matrix ist nur der Sonderfall des allgemeinen Problems. Für Ihre erste Frage siehe die Bearbeitung. D.=0
Arnold Neumaier
@Costis: Ich habe Schritt 2 etwas detaillierter hinzugefügt. - Wenn Sie den Antrag schreiben, senden Sie mir bitte einen Vorabdruck.
Arnold Neumaier
Danke für die Erklärung! Warum kann ich das überbestimmte System nicht einfach lösen , indem ich einen auf QR-Faktorisierung basierenden Ansatz verwende und alle Zeilen anstelle nur einer Teilmenge verwende? Ich denke, wenn die Anzahl der Spalten von C und B zunimmt, muss ich möglicherweise einige Zeilen entfernen, damit der Vorgang schneller ausgeführt wird. Klar, ich werde eine Beschreibung des Systems schreiben und diese per E-Mail an Sie senden. Ich denke tatsächlich, dass es möglich ist, ein anwendungsspezifisches Schema zu entwickeln, das möglicherweise besser funktioniert als der allgemeinste Fall. Vielen Dank! (C.+D.B.)yb'
Costis