QR - Alg mit Givens-Rotationen optimieren |
| 02.11.2010, 23:18 | Hamburger | Auf diesen Beitrag antworten » | ||
| QR - Alg mit Givens-Rotationen optimieren Ich kann euch verstehen, mein erster Eintrag und dann gleich so eine Frage 
Folgendes: Mittlerweile bin ich am Verzweifeln an meiner Aufgabe für die Nummerik Vorlesung. Ich soll ein Eigenwerteproblem lösen mit einer 150 x 150 Matrix. In das von meinem Prof. vorgegebenen Programm soll ich nun mithilfe der Givens-Rotationen dieses Problem lösen. Das Programm funktioniert auch soweit richtig (probiert an einem kleinen Zahlenbeispiel). Leider dauert es über eine Stunde die dünnbesetzte Matrix(150x150) auszurechnen und leider bekomme ich es nicht optimiert. Kann mir jemand euren fachlichen Rat anvertrauen?!?! Sicherlich wird es daran liegen, dass die Givens-Matrizen nur vier Elemente haben und nur mit diesen multipliziert müssen. Leider bekomme ich das in mein Programm nicht geschrieben 
Wäre sehr dankbar über eure Hilfe und ich könnte wieder ruhig schlafen !!! Hab schon einiges an Stunden reingesteckt, komme nur nicht weiter
Gruß |
||||
| 02.11.2010, 23:21 | tigerbine | Auf diesen Beitrag antworten » | ||
| RE: QR - Alg mit Givens-Rotationen OPTIMIEREN Hey, wie rechnest du die Matrizenmultiplikationen? Matrix mal Matrix oder hast du selbst eine Schleife gemacht?
Ansonsten: Und wenn man das wie im Theorieteil programmiert können Sie sehr schön sehen, wie die Rechenzeit schon bei dieser kleinen (praxisbezogen) Dimension sehr groß wird. 
Zeit zum Programm lesen habe ich nicht. Schau mal, ob du mit dem Code was anfangen kannst. [WS] Lineare Ausgleichprobleme |
||||
| 02.11.2010, 23:27 | Hamburger | Auf diesen Beitrag antworten » | ||
| RE: QR - Alg mit Givens-Rotationen OPTIMIEREN Die Berechnung meiner neuen "A" Matrix habe ich mittlerweile optimiert bekommen, so, dass nur noch die vier Elemente berücksichtigt werden. Nur bei dem "aufmultiplizieren" der einzelnen Givens-Matrizen "G" hapert es und ich komme einfach nicht drauf wie ich am geschicktesten die Schleifen schreibe. Daher läuft es zur Zeit noch mit der "normalen" Matrix mal Matrix Multiplikation und ist nachvollziehbar so langsam. Es müssen demnach ja alle Elemente multipliziert werden, obwohl ja 4 Multiplikationen ausreichen?!?! Gruß |
||||
| 02.11.2010, 23:32 | tigerbine | Auf diesen Beitrag antworten » | ||
| RE: QR - Alg mit Givens-Rotationen OPTIMIEREN Link angeschaut? |
||||
| 02.11.2010, 23:38 | Hamburger | Auf diesen Beitrag antworten » | ||
Den Link hatte ich schon gesehen und schon vorher mal drin gestöbert, aber so richtig kann ich das nicht umsetzen bzw. auf mein Problem übertragen. Hab, meiner Meinung nach, das irgendwie anschaulicher programmiert (wie man das so aus der Vorlesung eben mitbekommen kriegt
)Wie Multipliziere ich denn die j- und i-ten Elemente des aktuellen G`s am geschicktesten mit der vorigen G-Matrix auf?
"Ansonsten: Und wenn man das wie im Theorieteil programmiert können Sie sehr schön sehen, wie die Rechenzeit schon bei dieser kleinen (praxisbezogen) Dimension sehr groß wird." <--- Genau ja mein Problem |
||||
| 02.11.2010, 23:47 | tigerbine | Auf diesen Beitrag antworten » | ||
Ich bin schon ziemlich müde. Also nicht böse sein, wenn ich es nicht lösen kann.
Ich komme nicht hinter deine Idee, die Gs auf zumultiplizieren. Die Einträge des nächsten G hängen doch von dem ab, was das vorherige aus der Matrix A gemacht hat. Mal ein 3x3 Beispiel[WS] Lineare Ausgleichsprobleme - Beispiele Oder meinst du wie das Q^{-1} dann erzeugt wird? |
||||
| Anzeige | ||||
|
|
||||
| 03.11.2010, 00:00 | Hamburger | Auf diesen Beitrag antworten » | ||
Es ist auch schon bisschen spät für mich, vielleicht können wir ja morgen weiterschreiben?!?!
Würde mich sehr freuen, scheinst echt sehr hilfsbereit zu sein !!! 
!!!! DANKE SCHON EINMAL DAFÜR !!!! Genau, ich möchte gerne Ressourcenschonend das Q^(-1) erzeugen und dazu nach diesem Beispiel G21 * G31 multiplizieren um ganz am Schluss Q^(-1) * A = R zu berechnen. Beim A habe ich das folgender Maßen gelöst: a'pj = Upp · apj + Uqp · aqj a'qj = Upq · apj + Uqq · aqj |
||||
| 03.11.2010, 00:09 | tigerbine | Auf diesen Beitrag antworten » | ||
Weiß noch nicht, wann ich morgen on bin. Der Algo aus dem Link bestimmt imho die lösung eines LGs, gibt aber nicht A als Q*R aus. Das willst du aber? [nur dass ich weiß, was wir suchen] du hast die G-Matrizen also alle abgespeichert? oder klatschen wir die in der großen Schleife am ende immer zusammen? Dann kommt die neue MAtrix doch auch von links an die Alte. A stand doch auch rechts.... 
|
||||
| 03.11.2010, 00:17 | Hamburger | Auf diesen Beitrag antworten » | ||
Machen wir folgendes: Ich schreibe morgen noch einmal all meine Schritte zusammen (Quellcode kommentiert) und an welcher Stelle ich DIE Optimierung einbringen möchte (bzw glaube die viel bringt), damit es schneller funktioniert. Aber Grundsätzlich möchte ich gerne die G-Matrizen "aneinander klatschen" mit einer Schleife. Ist wahrscheinlich einfach zu spät jetzt
Und dann haben wir beide die gleiche Ausgangsbasis
Möchte mich nochmal sehr für die Unterstützung bedanken! Gruß & Gute Nacht ! |
||||
| 03.11.2010, 00:23 | Hamburger | Auf diesen Beitrag antworten » | ||
Sprich, meine Frage ist eigentlich nur: Wie "klatsche" ich möglichst geschickt die Givens-Matrizen hintereinander? Oder anders gefragt: Wie schreibe ich das Matrizen-Produkt am besten? Bislang mache ich es jedes mal über eine Matrizen-Multiplikation und das dauert entsprechend (zu)lange. |
||||
| 03.11.2010, 07:47 | Hamburger | Auf diesen Beitrag antworten » | ||
Guten Morgen, hab zwar nicht viel geschlafen, aber nun erstmal der Code: !--------------------------- Beginn QR - Algorithmus ------------------- do k=1, 100 A_temp = A U = Id !--------------------------- Beginn Givens-Rotation -------------------- do p = 1, NDIM-1 do q = p+1, NDIM U_temp = Id IF (A_temp(p,q) .NE. 0) then w = 1.0/(sqrt((A_temp(p,p))**2.0+(A_temp(q,p))**2.0)) varqp = -A_temp(q,p)*w varpq = A_temp(q,p)*w varpp = A_temp(p,p)*w varqq = A_temp(p,p)*w U_temp(q,p) = varqp U_temp(p,q) = varpq U_temp(p,p) = varpp U_temp(q,q) = varqq U = U_temp * U 
UM DIESE MULTIPLIKATION HANDELt ES SICHA_temp_old = A_temp do j = 1, NDIM A_temp(p,j) = varpp * A_temp_old(p,j) + varpq * A_temp_old(q,j) A_temp(q,j) = varqp * A_temp_old(p,j) + varqq * A_temp_old(q,j) end do End IF end do end do !--------------------------- Ende Givens-Rotation -------------------- A = A_temp *transpose(U) end do Wäre toll, wenn mir hier jemand noch helfen könnte. Gruß |
||||
| 03.11.2010, 18:09 | tigerbine | Auf diesen Beitrag antworten » | ||
Siehe pn, viel Zeit habe ich nicht. G ist doch sehr schwach besetzt. Mach dir an einem kleinen Beispiel klar, was mit einer (beliebigen) Matrix passiert, wenn man G von links dran multipliziert. Welche Einträge werden eigentlich nur aufsummiert. Im Algo musst du natürlich einbauen, wo das aktuelle G von der Einheitsmatrix abweicht. |
||||
| 06.11.2010, 15:10 | Hamburger | Auf diesen Beitrag antworten » | ||
Soo... Ich hab mich nochmal selber drangesetzt. Nun ist die Rechenzeit von über einer Stunde auf gute 5 Minuten gefallen. Hinsichtlich Fortran sieht vielleicht noch jemand optimierungspotenzial?!?! Gruß Id = 0.0 do i = 1, NDIM j = i Id(i,j) = 1 end do v = Id A_temp = A U = Id !--------------------------- Beginn Givens-Rotation -------------------- do p = 1, NDIM-1 do q = p+1, NDIM ! Vorbereiten des temporären U U_temp = Id IF (abs(A_temp(q,p)) .GT. eps) then w = 1.0/(sqrt((A_temp(p,p))**2.0+(A_temp(q,p))**2.0)) varqp = -A_temp(q,p)*w varpq = -varqp varpp = A_temp(p,p)*w varqq = varpp Matrix = u do i = 1, NDIM ! IF (abs(u(p,i)) .GT. eps .and. ! & abs(u(q,i)) .GT. eps) then Matrix(p,i) = varpp*u(p,i) + varpq*u(q,i) Matrix(q,i) = varqp*u(p,i) + varqq*u(q,i) ! end IF end do u = Matrix A_temp_old = A_temp do i = 1, NDIM ! IF (abs(A_temp_old(p,i)) .GT. eps .and. ! & abs(A_temp_old(q,i)) .GT. eps) then A_temp(p,i) = varpp * A_temp_old(p,i) + varpq * A_temp_old(q,i) A_temp(q,i) = varqp * A_temp_old(p,i) + varqq * A_temp_old(q,i) ! end IF end do End IF end do end do !--------------------------- Ende Givens-Rotation -------------------- Matrix = 0.0 do j = 1, ndim do i = 1, ndim do l= 1, ndim IF (abs(U(i,l)) .GT. eps .and. abs(v(l,j)) .GT. eps) then Matrix(i,j) = Matrix(i,j) + U(i,l) * v(l,j) END IF end do end do end do v = Matrix Matrix = 0.0 do j = 1, ndim do i = 1, ndim do l= 1, ndim IF (abs(A_temp(i,l)) .GT. eps .and. abs(U(j,l)) .GT. eps) then Matrix(i,j) = Matrix(i,j) + A_temp(i,l) * U(j,l) END IF end do end do end do A = Matrix Schönes Wochenende !!! |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
