2
$\begingroup$

The Strassen Algorithm for computing $AB$ where $A$ and $B$ are two even matrices involves splitting the matrices into submatrices and then reducing the number of multiplications by $1$ from $8$ to $7$ through some magic. I'd like to reduce the number of multiplications from $7$ to $5$ in the case of squaring a matrix: $AA$. I understand that after the first step of the algorithm, when I do the recursive call, this doesn't actually work because I will no longer be squaring matrices, however, I'd like to prove that it is possible to do so.

Starting from the Strassen Algorithm, you have:

$M_1 = (A+C)(A+B)$

$M_2 = (B+D)(C+D)$

$M_3 = (A-D)(A+D)$

$M_4 = D(C-A)$

$M_5 = (A+B)D$

$M_6 = (C+D)A$

$M_7 = A(B-D)$

Where $A,B,C,D$ are the sub-matrices. In an attempt to look to combine some of these equations, it seems like $1$ and $5$ could be combined, and $2$ and $6$ as well. However, the order of the multiplications doesn't work, and even if it did, I wouldn't be able to get some of the other products.

Is there anything obvious that I'm missing? (Perhaps "obvious" isn't the right word)

$\endgroup$
2
  • $\begingroup$ If you could I think it would be part of the algorithm $\endgroup$
    – qwr
    Feb 5 '14 at 4:33
  • $\begingroup$ The idea is that even if you could, it doesn't affect the algorithm run-time because your recurrence relation only satisfies T(n) = 5T(N/2) + O(N) for the first recurrence. However, once you go to the second recurrence, because you are computing the matrix multiplications M_1, M_2, etc, and you are no longer squaring matrices, the number of multiplications would go back up to the general case giving you T(N) = 7T(N/2)+O(N). I simply want to show that for the first step, you can use only 5 multiplications. $\endgroup$
    – Teofrostus
    Feb 5 '14 at 5:00
2
$\begingroup$

I'm not sure if this is exactly what you what you are asking, but the smallest recursion case, a 2x2 matrix, can be squared with 5 multiplications.

Squaring the matrix with a, b, c, d requires multiplications a^2, d^2, bc, b(a+d), c(a+d) which is evident just by performing the multiplication by hand.

$\endgroup$
1

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.