2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ # of operation depends on the size of the matrix. Do you know the formula? $\endgroup$ – Memming Feb 19 '16 at 13:26
  • $\begingroup$ 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 $\endgroup$ – Parisa Feb 19 '16 at 14:20
  • 3
    $\begingroup$ 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...) $\endgroup$ – Christian Clason Feb 19 '16 at 15:02
  • 2
    $\begingroup$ 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). $\endgroup$ – Christian Clason Feb 19 '16 at 16:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Christian Clason Feb 19 '16 at 16:06
7
$\begingroup$

The answer to this question depends heavily on the particular details of the computer that you're using.

In modern implementations, conventional matrix multiplication implementation (in the form of highly optimized versions of the BLAS xGEMM function) use blocked algorithms that are carefully tuned to match the cache size of the processor. In comparison, Strassen's algorithm is extremely cache unfriendly, and this makes it difficult to get good performance on contemporary processors.

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:

Austin R. Benson and Grey Ballard. A Framework for Practical Parallel Fast Matrix Multiplication. http://arxiv.org/pdf/1409.2908.pdf

There's another important issue to consider here- Strassen like algorithms are less numerically accurate than conventional blocked matrix-matrix multiplication. In some applications that inaccuracy can cause problems at the application level. Because of this, and because the performance improvements are not that large for reasonably sized matrices, few people make use of Strassen like algorithms in practice.

$\endgroup$
  • 4
    $\begingroup$ It's also very rarely the case that most of your CPU time is spent in matrix-matrix multiplications. The performance advantage to be had from Strassen multiplication won't matter unless you're spending a significant amount of time on large dense matrix multiplications. $\endgroup$ – Brian Borchers Feb 19 '16 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.