AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein [Java] Matrixmultiplikation nach Schönhage
Thema durchsuchen
Ansicht
Themen-Optionen

[Java] Matrixmultiplikation nach Schönhage

Ein Thema von 3_of_8 · begonnen am 12. Mai 2006 · letzter Beitrag vom 13. Mai 2006
Antwort Antwort
Seite 1 von 2  1 2      
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#1

[Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 21:45
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.
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
pszopp

Registriert seit: 7. Sep 2005
Ort: Alsdorf
95 Beiträge
 
Delphi 2010 Professional
 
#2

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 22:07
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
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#3

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 22:10
i ist der Spaltenindex und j der Zeilenindex. Also ist es nicht korrekt und ich muss die beiden vertauschen oder wie?
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Benutzerbild von MagicAndre1981
MagicAndre1981

Registriert seit: 4. Jun 2004
Ort: Nordhausen
2.214 Beiträge
 
Delphi 7 Enterprise
 
#4

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 22:18
was ist den der Schönhage-Algotithmus überhaupt? Haste da eine Erklärung/Definition von?
André
"A programmer is just a tool which converts caffeine into code", daran wirds wohl liegen, dass ich Abends nie pennen kann

Zitat von Luckie:
Nicht nur dass ihr offtopic geworden seid, jetzt werdet ihr selber im Offtopic noch offtopic
  Mit Zitat antworten Zitat
pszopp

Registriert seit: 7. Sep 2005
Ort: Alsdorf
95 Beiträge
 
Delphi 2010 Professional
 
#5

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 22:25
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?
  Mit Zitat antworten Zitat
Benutzerbild von JasonDX
JasonDX
(CodeLib-Manager)

Registriert seit: 5. Aug 2004
Ort: München
1.062 Beiträge
 
#6

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 22:31
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
Mike
Passion is no replacement for reason
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#7

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 22:33
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.
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#8

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 23:29
@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
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#9

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 12. Mai 2006, 23:37
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);
          }
      }   

}
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#10

Re: [Java] Matrixmultiplikation nach Schönhage

  Alt 13. Mai 2006, 01:09
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.
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 03:20 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz