[Java] Matrixmultiplikation nach Schönhage

[3_of_8]

Morgen.

Ich hab ein Problem. Die zweite Uni-Aufgabe ist "Matrixmultiplikation nach dem Schönhage-Verfahren"

Problem: Matrixmultiplikation ist ein bisschen kompliziert für einen Neuntklässler.

Ich hab schon mal folgenden Algorithmus geschrieben, der zwei Matrizen der Größe n*n multipliziert nach dem Standardverfahren:

Code:

public static Matrix stdMult(Matrix m1, Matrix m2) throws MMException {
    int n=m1.getSize();
    Matrix result=new Matrix(n);
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int value=0;
            for(int k=0; k<n; k++) {
                value+=m1.getElem(i,k)*m2.getElem(k,j);    
            }
            result.setElem(i,j,value);
        }
    }
    return result;          
}

So weit, so gut.
Ist dieser Algorithmus richtig? Und wenn ja, wie entwickle ich daraus jetzt einen rekursiven Schönhage-Algorithmus in der Funktion ssMult(Matrix m1, Matrix m2, int n0)?

(Wenn die größe der übergebenen Matrizen<=n0 ist, wird die Standardmultiplikation verwendet.)

Bei mir hängts momentan noch daran, dass ich keine Ahnung habe, wie so ein Schönhage-Algorithmus funktioniert.

[pszopp]

Hallo 3_of_8,

Das Verfahren stimmt, falls i den Zeilenindex und j den Spaltenindex darstellt.
Vielleicht solltest du noch prüfen ob die Matrix quadratisch ist (nxn).
Was den "Schönhage-Algorithmus" angeht: Hab noch nie davon gehört.


Viele Grüße,
pszopp

[3_of_8]

i ist der Spaltenindex und j der Zeilenindex. Also ist es nicht korrekt und ich muss die beiden vertauschen oder wie?

[MagicAndre1981]

was ist den der Schönhage-Algotithmus überhaupt? Haste da eine Erklärung/Definition von?

[pszopp]

Wenn man Matrizen multipliziert muss man darauf achten, dass das nicht assoziativ ist.
Also A*B ist nicht gleich B*A

Hier mal eine Beispiel-Multiplikation:

A =
|2 3|
|5 4|

B =
|1 3|
|2 4|

A * B =
|2*1+3*2 2*3+3*4|
|5*1+4*2 5*3+4*4|

=
|08 18|
|13 21|

In der Mathematik wird in der Regel zuerst die Zeile und dann die Spalte angegeben.
Also A(0, 1) heißt: von dem ersten Element oben links gehts
0 nach unten und
einen nach rechts.
Also ist hier A(0, 1) = 3.

Wenn ich das richtig sehe, ist das bei dir anderherum.
Für Java gibt es doch auch das JAMA-Package, das schon eingie std. Methode beinhaltet.
Ist das nicht interessant für dich?

[JasonDX]

Zitat von MagicAndre1981:

was ist den der Schönhage-Algotithmus überhaupt?

Siehe Wikipedia: Schönhage-Strassen-Algorithmus
Genauere Beschreibung davon hab ich noch nicht gefunden, aber wenn ich mich nicht ganz verlesen hab beinhaltet er die schnelle Fourier-Transformation, IMO wird das a bissl heftig fuer nen 9tklaessler....

greetz
Mike

[3_of_8]

Tja, kann ich auch nix dafür. Mein Dozent hat entschieden, dass das die zweite Aufgabe ist. Ich glaube, ich habe endlich einen Algorithmus. Der funktioniert natürlich noch nicht (zwar ungetestet, aber nach Murphy's Law sehr wahrscheinlich), aber ich krieg das irgendwie hin. Hab ja noch ein paar Wochen Zeit.

[negaH]

@JasonDX:

Der Link zu Wikipedia beschreibt die "modulare Fermat Fast Fourier Transformation nach Schönhage/Strassen". Das ist was komplett anderes als die Matrix-Multiplikation nach Schönhage. Auch wenn beide Verfahren die gleiche Idee als logische Grundlage besitzen.

Die schnelle Multiplikation wie sie bei Wikipedia beschrieben wird habe ich selber schon programmiert. Von der Matrix-Multiplikation nach Schönhage habe ich ebenfalls schon gehört, aber selber noch nicht benutzt.

Gruß Hagen

[3_of_8]

Ich poste mal meine Klasse, da ich den Fehler einfach nicht finde.

Also stdMult funktioniert, ssMult hingegen ganz und gar nicht.

Code:

package matrix;

public class Matrix {
    
      private double[][] matrix;
    
      public static class MMException extends Exception {
          
          public MMException() {
              
          }
          
          public MMException(String message) {
              super(message);
          }
          
      }

      public Matrix(int n) {
          matrix=new double[n][n];
      }   
      
      public String toString() {
          int n=matrix.length;
          String result="";
          for(int i=0; i<n; i++) {
              for(int j=0; j<n; j++){
                  result+=String.format("%1.2f ",matrix[j][i]);
              }
              result+="\n";
          }
          return result;
      }
      
      public int getSize() {
          return matrix.length;
      }   
      
      public double getElem(int i, int j) throws MMException {
          return matrix[i][j];
      }   
      
      public void setElem(int i, int j, double x) throws MMException {
          matrix[i][j]=x;
      }
      
      public Matrix getSubMatrix(int left, int top, int n) throws MMException{
          if(n<1) {
              return new Matrix(0);
          }
          Matrix result=new Matrix(n);
          for(int i=0; i<n; i++) {
              for(int j=0; j<n; j++) {
                  result.setElem(i,j,matrix[i+left][j+top]);
              }
          }
          return result;
      }
      
      public static Matrix add(Matrix m1, Matrix m2) throws MMException {
          if(m1==null||m2==null) {
              throw new MMException("Matrices must not be null.");
          }
          int n=m1.getSize();
          Matrix result=new Matrix(n);
          for(int i=0; i<n; i++) {
              for(int j=0; j<n; j++) {
                  result.setElem(i,j,m1.getElem(i,j)+m2.getElem(i,j));
              }
          }
          return result;
      }
      
      public Matrix add(Matrix m2) throws MMException {
          return add(this,m2);
      }
      
      public static Matrix subtract(Matrix m1, Matrix m2) throws MMException {
          if(m1==null||m2==null) {
              throw new MMException("Matrices must not be null.");
          }
          int n=m1.getSize();
          Matrix result=new Matrix(n);
          for(int i=0; i<n; i++) {
              for(int j=0; j<n; j++) {
                  result.setElem(i,j,m1.getElem(i,j)-m2.getElem(i,j));
              }
          }
          return result;
      }
      
      public Matrix subtract(Matrix m2) throws MMException {
          return add(this,m2);
      }
      
      public static Matrix stdMult(Matrix m1, Matrix m2) throws MMException {
          if(m1==null||m2==null) {
              throw new MMException("Matrices must not be null.");
          }
          int n=m1.getSize();
          Matrix result=new Matrix(n);
          for(int i=0; i<n; i++) {
              for(int j=0; j<n; j++) {
                  int value=0;
                  for(int k=0; k<n; k++) {
                      value+=m1.getElem(j,k)*m2.getElem(k,i);    
                  }
                  result.setElem(i,j,value);
              }
          }
          return result;          
      }
      
      public Matrix stdMult(Matrix m2) throws MMException {
          return stdMult(this, m2);
      }
      
      public static Matrix ssMult(Matrix m1, Matrix m2, int n0) 
          throws MMException{
          int n=m1.getSize();
          if(n<n0||n<3) {
              return stdMult(m1,m2);
          } else {
              /*
               * Dividing the two matrices into 4 submatrices each and poke
               * them into some variables.
               */
              Matrix m1TopLeft=m1.getSubMatrix(0,0,(int)n/2);
              Matrix m1TopRight=m1.getSubMatrix((int)n/2,0,(int)n/2);
              Matrix m1BottomLeft=m1.getSubMatrix(0,(int)n/2,(int)n/2);
              Matrix m1BottomRight=m1.getSubMatrix((int)n/2,(int)n/2,
                  (int)n/2);
              
              Matrix m2TopLeft=m2.getSubMatrix(0,0,(int)n/2);
              Matrix m2TopRight=m2.getSubMatrix((int)n/2,0,(int)n/2);
              Matrix m2BottomLeft=m2.getSubMatrix(0,(int)n/2,(int)n/2);
              Matrix m2BottomRight=m2.getSubMatrix((int)n/2,(int)n/2,
                  (int)n/2);
              
              /*
               * Defining and setting the seven auxiliary matrices
               */
              Matrix a1=ssMult(subtract(m1TopRight,m1BottomRight),
                  add(m2BottomLeft,m2BottomRight),n0);
              Matrix a2=ssMult(add(m1TopLeft,m1BottomRight),
                      add(m2TopLeft,m2BottomRight),n0);
              Matrix a3=ssMult(subtract(m1TopLeft,m1BottomLeft),
                      add(m2TopLeft,m2TopRight),n0);
              Matrix a4=ssMult(add(m1TopLeft,m1TopRight),m2BottomRight,n0);
              Matrix a5=ssMult(m1TopLeft,
                      subtract(m2TopRight,m2BottomRight),n0);
              Matrix a6=ssMult(m1BottomRight,
                      subtract(m2BottomLeft,m2TopLeft),n0);
              Matrix a7=ssMult(add(m1BottomLeft,m1BottomRight),m2TopLeft,n0);
              
              Matrix c11=subtract(add(a1,a2),subtract(a4,a6));
              Matrix c21=add(a4,a5);
              Matrix c12=add(a6,a7);
              Matrix c22=add(subtract(a2,a3),subtract(a5,a7));
              
              Matrix result=new Matrix(n);
              for(int i=0; i<(int)n/2; i++){
                  for(int j=0; j<(int)n/2; j++){
                      result.setElem(i,j,c11.getElem(i,j));
                  }
              }
              for(int i=0; i<(int)n/2; i++){
                  for(int j=0; j<(int)n/2; j++){
                      result.setElem(i+(int)n/2,j,c12.getElem(i,j));
                  }
              }
              for(int i=0; i<(int)n/2; i++){
                  for(int j=0; j<(int)n/2; j++){
                      result.setElem(i,j+(int)n/2,c21.getElem(i,j));
                  }
              }
              for(int i=0; i<(int)n/2; i++){
                  for(int j=0; j<(int)n/2; j++){
                      result.setElem(i+(int)n/2,j+(int)n/2,c22.getElem(i,j));
                  }
              }

              return result;
          }
      }
      
      public Matrix ssMult(Matrix m2, int n0) throws MMException {
          if(matrix.length<n0||matrix.length<3) {
              return stdMult(this,m2);
          } else {
              return ssMult(this,m2,n0);
          }
      }   

}

[3_of_8]

Argh! Das war so was von einfach! Der Algorithmus funktioniert! Jetzt muss ich nur noch an der Shell und an den Kommentaren arbeiten, damit mein Prof nix zu meckern hat.