Question

Strassen’s algorithm for matrix multiplication relies on using 7 multiplications (instead of 8 as in the straightforward algorithm) to multiply a pair of 2 by 2 matrices. Explain why it is not possible to further reduce this number, 7, to anything less than 4, in multiplying a pair of 2 by 2 matrices.

Answer 1

Hey so you want to know why we cannot reduce those 7 multiplications even more, well I can answer that for you and make you understand why we cannot further reduce that 7 number for a 2 by 2 matrix.

There are reason why those multiplications should be at least 7, the reason are:-

The submatrices in recursion take extra space.

You see whenever we are multiplying a 2 by 2 matrix(for this example) we would just simply not be able to have 4 multiplications as you said because 4 multiplications are done on the first iteration itself.

And I'm sure as you know Strassen's algo doesn't do only one iteration, it does multiple iterations to multiply 2 by 2 matrices, and in doing those iterations the total number of multiplications also go up.

In the end we can certainly reduce the number of multiplications but only up to a certain number and that number is 7, not 4 because number of iterations are always going to be greater than 1. Hope you understand it now.