troubleshooting Question

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

Programming Languages-OtherJavaAlgorithms
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[][] _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));

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!
###### 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.