Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

Question

Strassen's algorithm uses the divide and conquer approach to divide the matrix multiplication of two nxn matrices to multiplication of 7 2x2 matrices to get an overall complexity O(n^c) where c=log_2(7). I also read a paper which proved that it was impossible to multiply two 2x2 matrices in less than 7 multiplication operations.

So my question is, what's so special about 2x2? Why not break the original matrix multiplication to 3x3 matrix multiplication. Surely, if we can make the multiplication in 21 multiplications or less, then we would have a better result than dividing it to 2x2. And then why stop at 3x3, when you can divide the problem to 4x4, or in general axa?

Answer 1

There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The special thing about 2×2 matrices are that they are the smallest square matrices which are larger than 1×1.

You can read more in this recent survey by Dumas and Pan on fast matrix multiplication, which concentrate on practical algorithms.

From a pure mathematical point of view, the following theorem is known:

Suppose that the algebraic complexity of matrix multiplication is $O(n^\alpha)$. Then for every $\epsilon > 0$ there is a divide-and-conquer algorithm for multiplying matrices in $O(n^{\alpha+\epsilon})$.

Here a divide-and-conquer algorithm is an algorithm which recursively applies some smart algorithm for multiplying $m\times m$ matrices, for some constant $m$.

The fastest theoretical algorithm for matrix multiplication, due to Le Gall, is based on the classical algorithm of Coppersmith and Winograd. Unfortunately, this algorithm isn't practical.