3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You'd need to calculate 9 sums from 27 products, but find 21 clever products of sums instead so that these 9 sums can be produced as sums/differences of those 21 products. That seems difficult. You have to save 6 of 27 products. Nothing keeps you from trying. $\endgroup$ – gnasher729 Feb 18 '17 at 15:56
3
$\begingroup$

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.

$\endgroup$

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.