troubleshooting Question

Matrix Multiplication - Divide & Conquer vs Strassen, Divide & Conquer is coming out as being faster, why?

Avatar of nocturn4l
nocturn4l asked on
Programming Languages-OtherJavaAlgorithms
55 Comments2 Solutions9012 ViewsLast Modified:
From what I understand, Strassen's method for multiplying Matrices should be the fastest... but the Divide & Conquer method is clearly the fastest in my testing... Am I doing something wrong? Or is this correct?

The instructions were: "The total time spent is then divided by the number of times the algorithm is performed to obtain the time taken to solve the given instance"

So I just have an individual "counter++" in every method and divide the time "recorded time/ counter++".. (hopefully this is correct)

So far here are my times: (in order top/down: classic, divide & conquer, strassen) (size = size of matrix)

size 2

Time Elapsed:8660 nano-seconds

Time Elapsed:3849 nano-seconds

Time Elapsed:5377 nano-seconds

size 4

Time Elapsed:24864 nano-seconds

Time Elapsed:3080 nano-seconds

Time Elapsed:5229 nano-seconds

size 8

Time Elapsed:125435 nano-seconds

Time Elapsed:2920 nano-seconds

Time Elapsed:5196 nano-seconds

size 16

Time Elapsed:867149 nano-seconds

Time Elapsed:1559 nano-seconds

Time Elapsed:2853 nano-seconds

size 32

Time Elapsed:5191721 nano-seconds

Time Elapsed:972 nano-seconds

Time Elapsed:1722 nano-seconds

size 64

Time Elapsed:8155785 nano-seconds

Time Elapsed:874 nano-seconds

Time Elapsed:1696 nano-seconds




Example of how I'm testing the time:
System.out.println("\nStrassen Multiplication Matrix:");
    startTime = System.nanoTime();
    temp = m.strassen(m.m1, m.m2);
    endTime = System.nanoTime();
    m.print(temp);
    System.out.println("Time Elapsed:" + (endTime - startTime)/m.count_strassen + " nano-seconds");


DIVIDE & CONQUER CODE
if (n == 1) {
            result[0][0] = a[0][0] * b[0][0];
        }
        else {
            int[][] a11 = new int[n/2][n/2];
            int[][] a12 = new int[n/2][n/2];
            int[][] a21 = new int[n/2][n/2];
            int[][] a22 = new int[n/2][n/2];
            int[][] b11 = new int[n/2][n/2];
            int[][] b12 = new int[n/2][n/2];
            int[][] b21 = new int[n/2][n/2];
            int[][] b22 = new int[n/2][n/2];

            initialize(a, a11, 0 , 0);
            initialize(a, a12, 0 , n/2);
            initialize(a, a21, n/2, 0);
            initialize(a, a22, n/2, n/2);
            initialize(b, b11, 0 , 0);
            initialize(b, b12, 0 , n/2);
            initialize(b, b21, n/2, 0);
            initialize(b, b22, n/2, n/2);

            int[][] c11 = add(divideandconq(a11, b11), divideandconq(a12, b21));
            int[][] c12 = add(divideandconq(a11, b12), divideandconq(a12, b22));
            int[][] c21 = add(divideandconq(a21, b11), divideandconq(a22, b21));
            int[][] c22 = add(divideandconq(a21, b12), divideandconq(a22, b22));

            putTogether(c11, result, 0 , 0);
            putTogether(c12, result, 0 , n/2);
            putTogether(c21, result, n/2, 0);
            putTogether(c22, result, n/2, n/2);
        }
        return result;

if (n == 1) {
            result[0][0] = a[0][0] * b[0][0];
        }
    else {
        int[][] a11 = new int[n/2][n/2];
        int[][] a12 = new int[n/2][n/2];
        int[][] a21 = new int[n/2][n/2];
        int[][] a22 = new int[n/2][n/2];
        int[][] b11 = new int[n/2][n/2];
        int[][] b12 = new int[n/2][n/2];
        int[][] b21 = new int[n/2][n/2];
        int[][] b22 = new int[n/2][n/2];

        initialize(a, a11, 0 , 0);
        initialize(a, a12, 0 , n/2);
        initialize(a, a21, n/2, 0);
        initialize(a, a22, n/2, n/2);
        initialize(b, b11, 0 , 0);
        initialize(b, b12, 0 , n/2);
        initialize(b, b21, n/2, 0);
        initialize(b, b22, n/2, n/2);

        int[][] _m1 = strassen(add(a11, a22), add(b11, b22));
        int[][] _m2 = strassen(add(a21, a22), b11);
        int[][] _m3 = strassen(a11, minus(b12, b22));
        int[][] _m4 = strassen(a22, minus(b21, b11));
        int[][] _m5 = strassen(add(a11, a12), b22);
        int[][] _m6 = strassen(minus(a21, a11), add(b11, b12));
        int[][] _m7 = strassen(minus(a12, a22), add(b21, b22));

        int[][] c11 = add(minus(add(_m1, _m4), _m5), _m7);
        int[][] c12 = add(_m3, _m5);
        int[][] c21 = add(_m2, _m4);
        int[][] c22 = add(minus(add(_m1, _m3), _m2), _m6);

        putTogether(c11, result, 0 , 0);
        putTogether(c12, result, 0 , n/2);
        putTogether(c21, result, n/2, 0);
        putTogether(c22, result, n/2, n/2);

    }
    return result;

SAMPLE OUTPUT I promise I did. Here's an example of my output for a matrix of size 4:

1st Random Generated Matrix: 10 57 33 70
6 12 38 70
20 41 65 98
83 0 31 73
2nd Random Generated Matrix: 11 70 54 79
2 51 38 71
27 53 37 86
48 87 20 41
Classic Multiplication Matrix: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
Time Elapsed:21232 nano-seconds

Divide and Conquer Multiplication Matrix: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
Time Elapsed:3042 nano-seconds

Strassen Multiplication Matrix: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
Time Elapsed:5303 nano-seconds
Join the community to see this answer!
Join our exclusive community to see this answer & millions of others.
Unlock 2 Answers and 55 Comments.
Join the Community
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 2 Answers and 55 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros