Determine when Strassen's algorithm for matrix multiplication is better than regular MM

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.

• 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). Oct 24, 2018 at 23:58
• @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? Oct 25, 2018 at 0:30
• Something like that, yes. Oct 25, 2018 at 1:37
• Unfortunately your method doesn't determine correctly the number of arithmetic operations performed by Strassen's algorithm. Oct 25, 2018 at 6:02
• @YuvalFilmus Do you have any suggestions? Oct 25, 2018 at 12:53

• There are several ways of defining Strassen's algorithm when $$n$$ is not a power of 2.
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}$$.