Hey, danke erstmal für eure ausführlichen Antworten.
Hätte den Sourcecode direkt mitposten sollen.
Also ich hab die Algorithmen allesamt mit kleineren 2x2, 3x3 getestet, und händisch ausgerechnet ob das Ergebnis stimmt, deswegen denke ich auch, dass es für größere geht. Die Algorithmen erscheinen mir auch sehr logisch.
Nun zum Code:
[SPOILER]```public Matrix multiply(Matrix bval) {
double [][] res = new double [val.length][bval.val[0].length];
double z,x;
if (val[0].length == bval.val.length){
for (int i=0; i< val.length; i++){
for (int j=0; j< bval.val[0].length; j++){
x=0;
for (int k=0; k<bval.val.length;k++){
z = val**[k] * bval.val[k][j];
x += z;
}
res**[j]=x;
}
}
return new Matrix(res);
}
throw new IllegalArgumentException();
}```[/SPOILER]
Das ist der Code für eine ganz normale serielle Multiplikation.
Komplexität sollte nach meinem Verständnis bei O(n³) liegen.
Der parallele Code ist dementsprechend sehr ähnlich:
[SPOILER]public ParallelMatrix multiply(Matrix B) { double[][] res = new double[val.length][B.val[0].length]; ParallelMatrix C = new ParallelMatrix(res); Thread[] threads = new Thread[val.length]; for (int i = 0; i < val.length; i++) { threads** = new MultThread(C,this,B,i); threads**.start(); } for (int i =0; i < val.length; i++ ) { try { threads**.join(); } catch (InterruptedException e) { e.printStackTrace(); } } return C; }[/SPOILER]
Die Thread run-Methode führt dann praktisch nur die inneren beiden for-Schleifen aus, wie sie auch im seriellen Code sind.
Soo. Und jetzt das für mich immer noch Erstaunliche:
Die Multiplikation mit einer transponierten Matrix.
Zuerst transponiere ich sie:
[SPOILER]public Matrix transpose() { double[][] res = new double[val[0].length][val.length]; for (int i = 0; i < val.length; i++) { for (int j = 0; j < val[0].length; j++) { res**[j] = val[j]**; } } return new Matrix(res); }[/SPOILER]
Dann multipliziere ich wieder. Praktisch genau nach dem gleichen Schema, wie schon im seriellen Code.
[SPOILER]```public Matrix multiply(Matrix B) {
double [][] res = new double [val.length][B.val[0].length];
double z,x;
Matrix Bt = B.transpose();
double[][] Bval = Bt.val;
if (val[0].length == Bval.length){
for (int i=0; i< val.length; i++){
for (int j=0; j< Bval[0].length; j++){
x=0;
for (int k=0; k<Bval.length;k++){
z = val**[k] * Bval[j][k];
x += z;
}
res**[j]=x;
}
}
return new Matrix(res);
}
return new Matrix(res);
}```[/SPOILER]
Komplexität sollte auch hier bei O(n³) liegen. Im Prinzip wurden nur die Indizes leicht angepasst, nachdem transponiert wurde.
Parallel sind das ganze dann wieder so aus wie schon zuvor. Nur eben leicht angepasst.
Lasse ich nun eine Zeitmessung laufen komme ich auf folgende Zeiten:
Seriell: 11064
Parallel: 3092
Transponiert Parallel: 237
Transponiert Seriell: 978
Hier mal der Source zur Zeitmessung. Da sollte alles mit rechten Dingen zugehen:
[SPOILER]```public void timing() {
Matrix aSeriell = new Matrix(a);
Matrix bSeriell = new Matrix(b);
ParallelMatrix aParallel = new ParallelMatrix(a);
ParallelMatrix bParallel = new ParallelMatrix(b);
ParallelTransMatrix aTrans = new ParallelTransMatrix(a);
ParallelTransMatrix bTrans = new ParallelTransMatrix(b);
TransMatrix aT = new TransMatrix(a);
TransMatrix bT = new TransMatrix(b);
long ts = System.currentTimeMillis();
aSeriell.multiply(bSeriell);
ts = System.currentTimeMillis() - ts;
System.out.println("Seriell: " + ts);
long tp = System.currentTimeMillis();
aParallel.multiply(bParallel);
tp = System.currentTimeMillis() - tp;
System.out.println("Parallel: " + tp);
long ttp = System.currentTimeMillis();
aTrans.multiply(bTrans);
ttp = System.currentTimeMillis() - ttp;
System.out.println("Transponiert Parallel: " + ttp);
long tts = System.currentTimeMillis();
aT.multiply(bT);
tts = System.currentTimeMillis() - tts;
System.out.println("Transponiert Seriell: " + tts);
}```[/SPOILER]
Die Messungen sind für zwei 1024x1024 Matrizen. Ich finde man sieht auch ganz schön, dass der Verhältnis gleich ist. Der normal-parallele ist ~3x so schnell wie der normal-serielle.
Der parallel-transponierte wiederum ~3x so schnell wie der transponiert-serielle.
Naja, man sieht ja deutlich, dass der transponiert-paralle “alles in den Schatten stellt”. Deswegen auch meine eigentliche Frage. Es geht ja im Prinzip nur mit quadratischen Matrizen, da sonst das Verhältnis der Zeilen bzw Spalten zueinander nicht mehr passt. Da ich mathematisches auch nicht wirklich bewandert bin, hab ich mir die Frage gestellt ob es nicht eine Möglichkeit gibt, diese gute Performance auch für nicht-quadratische Matrizen zu nutzen.
Grüße
#Den Test werde ich sofort mal laufen lassen.
Danke dafür.