Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
If you could I think it would be part of the algorithm –  qwr Feb 5 at 4: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 5 at 5:00

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.