2
$\begingroup$

I'm trying to find out how to determine the size of the matrices $n$ such that Strassen's algorithm for matrix multiplication is better than the regular algorithm. I know that Strassen's algorithm is $\Theta(n^{lg 7})$, and regular matrix multiplication is $\Theta(n^3)$.

My reasoning goes along the following lines:

When the size of the matrices to be multiplied is $2x2$, Strassen's algorithm carries out 7 multiplications and 24 additions, whereas the regular multiplication requires 8 multiplications and 4 additions.

So I can do something like this, by the definition of the $\Theta$ notation

\begin{align} 31 &= c_1 2^{lg 7} \\ 31/7& = c_1 \end{align}

Using a similar reasoning,

\begin{align} 12 &= c_22^{lg 8} \\ 12/8 &= c_2 \\ 3/2 &= c_2 \end{align}

If this is valid, having determined the constants all that remains is to set the equalities using these constants, and solve for $n$.

I would just like to know if my train of thought is correct, and if it isn't, how to go about finding the size of the matrix $n$ such that Strassen's algorithm is better. I know this might depend on specific implementations of hardware, architecture and so on, but the divide and conquer approach doesn't necessarily have to be used until the algorithm reaches the base case $2x2$. I want to know when to switch to another algoritm, which in this case is the regular matrix multiplication.

$\endgroup$
6
  • 1
    $\begingroup$ Keep in mind $\Theta(n^{\log 7})$ does not mean $c n^{\log 7}$, but within a constant factor of $c n^{\log 7}$. The $\Theta$s of Strassen's algorithm and naive multiplication do tell you that eventually Strassen's algorithm is more efficient but you can't use the $\Theta$ expressions themselves to find at exactly what $n$ the crossover occurs (and that $n$ might not be unique). You would want to directly solve the recurrence for the number of multiplications in Strassen's algorithm (which gets technical for non-power-of-two-sized matrices, if you care for that level of detail). $\endgroup$ Oct 24, 2018 at 23:58
  • $\begingroup$ @Solomonoff'sSecret I see. So I should solve the recurrences exactly, for which I would probably have to do a change of variable while assuming that $n$ is a power of 2. Once I get these constants, I can set the equalities? $\endgroup$
    – milongo
    Oct 25, 2018 at 0:30
  • $\begingroup$ Something like that, yes. $\endgroup$ Oct 25, 2018 at 1:37
  • $\begingroup$ Unfortunately your method doesn't determine correctly the number of arithmetic operations performed by Strassen's algorithm. $\endgroup$ Oct 25, 2018 at 6:02
  • $\begingroup$ @YuvalFilmus Do you have any suggestions? $\endgroup$
    – milongo
    Oct 25, 2018 at 12:53

2 Answers 2

1
$\begingroup$

If you look at the number of operations, it's obvious that you would do a matrix multiplication using the smallest number of operations. For 2x2 the direct method is best. You calculate for 3x3, 4x4, 5x5 etc. how many operations you need using the direct method, and how many you need using the Strassen method, performing (n/2) x (n/2) products using the fastest method.

If you look at execution time, that is dependent on the computer where you run it, so the point where Strassen is better also depends on the implementation. You would do the same thing as above, but instead of calculating the number of calculations, measure the execution time.

$\endgroup$
0
$\begingroup$

Your question is underspecified, for two reasons:

  • There are several ways of defining Strassen's algorithm when $n$ is not a power of 2.
  • You haven't defined how you determine which algorithm is better.

To handle the first problem, let us only consider values of $n$ which are powers of 2. As for the second problem, perhaps the proper way to determine which algorithm is better is to run both and to see which is better in practice. But as a proxy for that, let us count just the number of arithmetic operations in the algorithm, giving the same weight to additions and multiplications, somewhat unrealistically. For a $2\times2$ algorithm using $a$ additions and $m$ multiplications, the recurrence for the number of additions $a_n$ and multiplications $m_n$ of $n\times n$ matrices (where $n$ is a power of 2) are $$ a_1 = 0, m_1 = 1, a_{2n} = ma_n + an^2, m_{2n} = mm_n. $$ Solving these recurrences on a computer, we find that Strassen's algorithm first improves on the standard algorithm for $n = 2^{12}$.

$\endgroup$
1
  • $\begingroup$ That’s if you run the Strassen algorithm recursively down to 2x2. But that would be daft if Strassen is inferior for 600x600. If you use the standard method whenever it is better, Strassen is an improvement much earlier. $\endgroup$
    – gnasher729
    Oct 26, 2018 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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