CODEWITHSUNDEEP
javaalgorithmmatrix
Linell
Linell

Reputation: 749

Strassen's Algorithm Returning Zero

The idea is to create a timer that will return how long it takes to perform a certain function. I sat and coded a matrix class and a Strass function that should multiply that I feed into it.

The timer function works correctly in that it returns the time that it takes to execute the Strass function. However, the Strass function doesn't return a matrix that has been multiplied. It is a matrix of all zeroes. It's as if the Strass function isn't assigning anything to Matrix C. Ever.

For example, multiplying a 2x2 matrix gives the following result:

     0.00 // P1

 0.00     0.00  // the matrix after multiplication 
 0.00     0.00

 7102000 // the time it took to do this

The Strass function looks like this:

public static void Strass(Matrix A, Matrix B, Matrix C) {
    // It has been suggested that P1-P7 should be of size
    // A.size()/2. Changing this does not fix the problem.
    Matrix P1 = new Matrix(A.size());
    Matrix P2 = new Matrix(A.size());
    Matrix P3 = new Matrix(A.size());
    Matrix P4 = new Matrix(A.size());
    Matrix P5 = new Matrix(A.size());
    Matrix P6 = new Matrix(A.size());
    Matrix P7 = new Matrix(A.size());

    // if n = 1 then
    if (A.size() == 1) {
        C = A.times(B);
    } else {
        if (A.size() != B.size()) throw new RuntimeException("Somehow, the sizes of the matrices aren't equal.");
        int sizeOf = A.size();
        // The ungodly recursive calls.
        Strass(A.partition(1, sizeOf/2, 1, sizeOf/2).plus(A.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf)), B.partition(1, sizeOf/2, 1, sizeOf/2).plus(B.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf)), P1);
        Strass(A.partition(sizeOf/2+1, sizeOf, 1, sizeOf/2).plus(A.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf)), B.partition(1, sizeOf/2, 1, sizeOf/2), P2);
        Strass(A.partition(1, sizeOf/2, 1, sizeOf/2), B.partition(1, sizeOf/2, sizeOf/2+1, sizeOf).minus(B.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf)), P3);
        Strass(A.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf), B.partition(sizeOf/2+1, sizeOf, 1, sizeOf/2).minus(B.partition(1, sizeOf/2, 1, sizeOf/2)), P4);
        Strass(A.partition(1, sizeOf/2, 1, sizeOf/2).plus(A.partition(1, sizeOf/2, sizeOf/2+1, sizeOf)), B.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf), P5);
        Strass(A.partition(sizeOf/2+1, sizeOf, 1, sizeOf/2).minus(A.partition(1, sizeOf/2, 1, sizeOf/2)), B.partition(1, sizeOf/2, 1, sizeOf/2).plus(B.partition(1, sizeOf/2, sizeOf/2+1, sizeOf)), P6);
        Strass(A.partition(1, sizeOf/2, sizeOf/2+1, 1).minus(A.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf)), B.partition(sizeOf/2+1, sizeOf, 1, sizeOf/2).plus(B.partition(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf)), P7);


        C.addPart(1, sizeOf/2, 1, sizeOf/2, (P1.plus(P4)).minus(P5.plus(P7)));
        C.addPart(sizeOf/2+1, sizeOf, 1, sizeOf/2, (P2.plus(P4)));
        C.addPart(1, sizeOf/2, sizeOf/2+1, sizeOf, (P3.plus(P5)));
        C.addPart(sizeOf/2+1, sizeOf, sizeOf/2+1, sizeOf, (P1.plus(P3)).minus(P2.plus(P3)));

    }

}

I've tested the addPart function, and it is working correctly as far as I can tell. The same goes for the plus and minus functions. I did my best to go through and verify that I have all of the right sizes and numbers in all of the right locations, and I'm pretty darn sure that I do. So, somewhere in all of this, there is something amiss.

For reference and brevity, I've pasted all of the relevant code here.

Upvotes: 0

Views: 493

Answers (2)

Keith Randall
Keith Randall

Reputation: 23265

C = A.times(B); is incorrect. This assigns a new matrix to C, it does not modify the matrix object that was passed in.

Upvotes: 2

phkahler
phkahler

Reputation: 5767

You should first test with a 1x1 matrix multiply. Then a 2x2, then a 4x4. These will all be easy to verify. I would also like to point out that your code does not handle matrix dimensions that are not a power of 2, so don't try with a 100x100 matrix. Also strange is that P1 to P7 are the same size as A. Shouldn't they be A.Size()/2 ?

Upvotes: 0

Related Questions