2

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)

Richard J
  • 183
Teofrostus
  • 305
  • If you could I think it would be part of the algorithm – qwr Feb 05 '14 at 04:33
  • 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. – Teofrostus Feb 05 '14 at 05:00

1 Answers1

2

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.

user3281963
  • 21