Gaussian Elimination
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 7.5
Bei dem ParallelMatrixVectorMultiplier macht es doch keinen Sinn beispielsweise das Produkt einer 3x3 Matrix und einem 3x1 Vektor mit mehr als 3 Threads zu berechnen oder? Sollte numberOfThreads größer als 3 sein, darf ich den Überschuss dann ignorieren?
Man könnte die Threads zwar trotzdem (sinnvoll) verwenden, ignorieren darfst du sie dennoch.
Dürfen die Algorithmen in-place arbeiten oder müssen die Eingabearrays unverändert bleiben?
Also, wenn man bei parallelem Gauss in situ arbeitet, schlägt der TestCase fail.
Ich kopiere mir deshalb die Matrix und den Vektor, die ich bearbeite.
Wie übergebe ich den meinen Threads die Arbeitspakete? Ist das mit ner LinkedBlockingQueue ok, oder eher mist?
Dann machst du aber etwas sehr merkwürdiges! :scared:
Es geht schief, wenn man in der strikten unteren Dreiecksmatrix keine 0 speichert, sondern andere Werte. Wäre das A am Ende eine obere Dreiecksmatrix, würden weitere Gauss-Schritte des Algorithmus die Matrix unverändert lassen.
Man kann aber im unteren Dreieck die Multiplikatoren der Gauss-Schritte speichern. Das ist effizient, wenn man mehrere Gleichungssysteme mit der selben Systemmatrix lösen will, da man so einfach an die LR-Zerlegung der Matrix kommt.
EDIT: Außerdem ruiniert die Rückwärtssubstitution das Ergebnis, wenn man den Lösungsvektor in b speichert.
Wieso sollte das beispielsweise bei der LR-Zerlegung kaputt gehen? Die funktioniert wunderbar in-place.
Selbstredend.
Die funktioniert in-place, allerdings übergibt Java die Arrays nur als Referenzen. Damit werden bei mehrmaligem Aufruf der Methoden auf den gleichen Matrizen die Multiplikatoren in der L-Matrix und damit alle Einträge außer in der ersten Zeile verändert, da ja die Ursprungsmatrix zerstört wird. Würde man hier 0er eintragen, würde sich die Matrix auch bei mehrmaligen Gauss-Eliminationen nicht mehr verändern und in Zeilenstufenform bleiben. Das kommt daher, dass die in-place LR-Zerlegung darauf ausgelegt ist, dass man die Einträge von A am Ende getrennt betrachtet, was ein erneutes Aufrufen der Gauss-Elimination nicht tut.
Ich habe das Gefühl wir reden gerade ein wenig aneinander vorbei.
Darüber, dass die Schnittstelle, die Parallelisierungsart sowie der Berechnungsweg bei der LR-Zerlegung ein/e andere/r ist, sind wir uns hoffentlich mehr oder weniger einig.
Wenn du mir jetzt nochmal kurz aufzeigen möchtest, was du mit
meinst, dann kann ich dir womöglich auch weiter folgen. 
Ok, ein Beispiel: Betrachte
[1 2 3]
A = [2 3 4]
[3 4 6].Durch Gauss-Verfahren in Zeilenstufenform gebracht ist das dann
[1 2 3]
R = [0 -1 -2]
[0 0 1].In dieser Form hat die Methode auch kein Problem beim mehrmaligen Aufruf, da diese Zeilenstufenform bei erneuter Gauss-Elimination gleich bleibt.
Jetzt kann man aber mit dem gleichen Algorithmus in A dann Einträge so gespeichert haben:
[1 2 3]
A' = [2 -1 -2]
[3 2 1]Damit kann man leicht die LR-Zerlegung von A ermitteln:
[1 0 0] [1 2 3]
L = [2 1 0], R = [0 -1 -2],
[3 2 1] [0 0 1]das Gleichungssystem kann also genau wie oben durch Rückwärtssubstitution gelöst werden, wenn b mitverändert wird.
Jetzt hat Java aber dank Call-by-Reference in dem Array A die Matrix A’ gespeichert. Erneutes Aufrufen von solveEquations() berechnet damit dann die LR-Zerlegung von A’ = L + R - E(Einheitsmatrix):
[1 2 3]
A'' = [2 -5 -8]
[3 0.8 -10.4]und würde damit das LGS A’y = x <=> (L + R - E)y = x lösen (wenn x in b gespeichert wurde, ansonsten A’y = b), was ja nicht mehr äquivalent zu Ay = x (Ay = b) ist.
Somit kann es etwas ausmachen, welche Werte man in dem unteren Dreieck der Matrix (das “hier” ^^) speichert. Chefchen wird wohl (wie ich auch zuerst) die Matrix A’ in A speichern, weswegen genanntes Problem auftritt.
PS: Berechnungsweg ist der gleiche, da Gauß-Algorithmus nichts anderes als Berechnen der LR-Zerlegung ist.
Ups ich hatte mir die falsche Klasse → falschen Testcase angesehen. Jetzt weiß ich auch was du mit “mehrmaligem Aufruf” meintest.
Die solveEquations darf bei Speicherung der L-Matrix nicht in A erfolgen, sofern weitere Aufrufe auftreten können, ja.
Ich lehne mich jetzt mal weit aus dem Fenster und behaupte dies ist mit etwas Mehraufwand fixbar, was allerdings auch, je nachdem was außenerhalb der eigenen Klassen mit Matrix A angestellt wird, auch in die Hose gehen kann.
Der Berechnungsweg - ihn so als solchen zu bezeichnen war wohl nicht ganz korrekt - ist nicht ganz der gleiche, denn die Speicherung der L-Matrix entfällt (teilweise). Auch hab ich grad nicht im Kopf, was die LR-Zerlegung bei 0en in der Diagonale anstellt. Ansich hat man da allerdings einige Freiheiten.
Kurz: du hattest Recht 
Irgendwie stehe ich beim parallelen Gauss auf dem Schlauch…
Mir fällt nur eine Lösung ein bei der ich mindestens 1 Thread pro Matrixzeile brauche, weil ansonsten alle Threads im Barrier await festhängen, es aber keinen weiteren Thread für das letzte Arbeitspaket gibt, somit schöner Deadlock…
Jemand nen Tipp wie man das macht?
Einfach eine andere Zuteilung wählen und/oder die Barrier anders initialisieren.
Das ist ja genau mein Problem… Ich habe keine Idee wie ich das aufteilen soll^^
Einen Executor zu verwenden ist hier offensichtlich nicht das sinnvollste (gleichwohl es funktioniert). Dann übergibt man einem Thread eben notfalls mehr als eine Zeile.
Wie hast du den sonst deine Daten auf die Threads aufgeteilt? Wenn man sich mal ein paar Gedanken gemacht hat, kommt man eigentlich relativ fix auf ein-drei Methoden, die (fast) immer funktionieren.
Ich reih mich mal ein mit ich hab keine Ahnung wie ich Gauss ordentlich parallel mache.
Die LU Dekomposition find ich Schwachsinn, weil ich damit ja eigentlich schon mein Ergebniss habe. Mich interessiert doch bloß die untere Dreicksmatrix und dann setzte ich rückwärts ein.
Das andere was mir einfällt ist pro Stufenelement(e) einen Thread zu machen, aber das ist find ich auch Banane.
Mir tun die Tutoren, die das korrigieren müssen, jetzt schon leid. 
Du hast doch vorgegeben wie viele Threads du erzeugen sollst. Dementsprechend teilst du deine Stufenelemente darauf auf.