I have an assignment question such as follows: when using the Strassen algorithm we have 7 subproblems usually, and I suppose this applies to any two $n*n$ matrices and the run time is $O(n^{log_27})$. However when I have an example of two identical $2*2$ matrices and I have to multiply them, I can just square them and it will give me 5 subproblems. i.e.:
| A11 A12 | multiplied by | A11 A12 | will give: | A11A11 + A12A21 A11A12 + A12A22 |
| A21 A22 | | A21 A22 | | A21A11 + A22A21 A21A12 + A22A22 |
which is simply | A11^2 + A12A21 A12(A11+A22) |
| A21(A11+A22) A12A21 + A22^2 |
where the multiplications are in A11^2, A22^2, A21*(term), A12*(term), and A12*A21
Why can't I assume that the runtime will be $O(n^{log_25})$? Is it because it only applies to $2*2$ matrices and not n*n in general? Or would I have additional subproblems asides from the 5 subproblems for multiplication?
Best Answer
We cannot do it in $O(n^{\log_2 5})$ as matrix multiplication is not commutative. That means if $A$ and $B$ are matrices, $AB\ne BA$ for many values of $A$ and $B$.
For more clarity $$A_{11}*A_{12} + A_{12}*A_{22}\ne A_{12}*(A_{11}+A_{22})=A_{12}*A_{11} + A_{12}*A_{22}$$
Therefore, we cannot divide into 5 subproblems to improve on Strassens Algorithm.
See this for more details https://stackoverflow.com/questions/27543250/whats-wrong-with-strassens-method-to-compute-square-of-a-matrix