[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.