Matrix Multiplication - Divide & Conquer vs Strassen, Divide & Conquer is faster?

3
votes

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 / counter++"

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

SAMPLE OUTPUT 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

5
performancealgorithmmatrixmatrix-multiplicationdivide-and-conquer
Are you sure your divide & conquer algorithm gives correct results? Strassen is divide & conquer in its nature; there must be some reasons they do multiple add and multiplication that way. – pad
ya I actually print to the console all the matrices calculated and make sure they're all the same – user1189352
I agree with pad, make sure you're comparing the results. Not by hand. Calculate and print the mean-squared error. – Ben Voigt
I promise I did. I'll copy and paste a sample of my output (editing OP) – user1189352
"Calculate and print the mean-squared error." I'm not sure how to do that, or what that means really – user1189352

5 Answers

3
votes

The constant factor in Strassen is very high, so for most inputs, divide&conquer will be faster. Try running your tests with much larger matrices (thousands+ elements) to see if Strassen's overtakes divide&conquer

3
votes

Just an idea: don't run it once, run it a 100 times.

Actually, run it first a 100 times without recording the time, then a 100 times recording it. Or even thousands of times if you have the time, the more the better.

System.nanoTime() can be very inaccurate at times, especially on a modern computer when dozens of processes are running at the same time. The more runs, the less that inaccuracy affects the results. The initial non-timed attempts are to "ramp up" the Java VM, making sure that every class is loaded, memory allocation and garbage collection settles in a steady rhythm, and so on.

Another change that could improve the accuracy of your testing is to remove all kinds of System.out calls (or indeed any output) from the actual calculation code, as that just adds a constant overhead to both functions, distorting the result.

0
votes

Something is wrong with your "classic" implementation. There's no way it should be that much slower. Classic should be faster until you get to pretty big matrices. Certainly a 4x4 should be much, much faster with standard matrix multiplication.

0
votes

The Strassen's slower cause it's not cache-friendly, it's only "theoretically" the fastest. "cache-oblivious" algorithm, such as your divide and conquer one, is usually faster.

0
votes

Strassen's algorithm time complexity is but divide and conquer algorithm time complexity is (you know, is almost ).

When we are comparing some algorithms using O (or theta) function, we mean that they are faster (or slower) when the input size approaches infinity.

As you can see, for small values of n, an algorithm with time complexity may be slower than an algorithm with time complexity. It's because of the constant factor (which only shows its effects when the input size is small).

chart

So, if your input size is small use the fastest algorithm you know. But if your input size is very large, use an algorithm with the minimum asymptotic time complexity.