# strassen algorithm vs. standard multiplication for matrices

I am trying to figure out at exactly what dimension it is better to use Strassen algorithm rather than the standard multiplication. I know that there is 18 addition and subtraction in Strassen algorithm but I don't know how I must calculate it. This is a homework so I don't want direct answer without any explanation. Any help is appreciated.

• # of operation depends on the size of the matrix. Do you know the formula? Feb 19 '16 at 13:26
• I know the formula of the strassen matrix. The question is like this: On which n (which n is the dimension of our matrices and the two matrices have the same size and n = 2^k) it is beneficial to use strassen algorithm rather than the standard algorithm. @Memming Feb 19 '16 at 14:20
• So all you need to know is the formula for the standard algorithm, equate the two and solve for $n$. (Or, if you're lazy, use a computer to evaluate both for $n=1,2,\dots$ and see at which point you get the bigger number for Strassen...) Feb 19 '16 at 15:02
• I don't think that's correct; in fact, I'm dubious about your count of 18 operations. Strassen's algorithm is a rather complicated divide-and-conquer algorithm, so the number of operations will involve the logarithm of $n$. If you want to cheat a bit, you can look at the Wolfram MathWorld entry on Strassen's Formula, which contains a bit of explanation (and the correct number -- you're off by a factor of about 4). Feb 19 '16 at 16:03
• From the entry, you can see that there are 18 additions and subtractions for a $2\times 2$ matrix; it seems you have also forgotten to count the multiplications. Feb 19 '16 at 16:06

One recent Arxiv preprint claims that a Strassen like algorithm can give modest performance improvements (up to about 25% faster) than Intel's MKL for matrices of size $N=3000$ or larger on an Intel processor based system: