-1
$\begingroup$

So I am clear with the basic Strassen's algorithm. For a regular 2*2 matrix, it will perform 7 multiplications instead of the conventional 8 for regular matrix multiplication algorithms. The seven products- P1 through P7 can be used to perform additions and subtraction to get the final multiplied matrix.

However if I have two matrices A and B, each being a 4*4 matrix, then how is Strassen's algorithm applied here? Since the way I have studied this algorithm explains it using a square matrix only, I can't seem to figure out the process for a 4*4 matrix.

From what I feel, maybe each of the 4*4 matrix could be recursively broken down into two sqUare matrices, but even if that's the correct approach, I'm stuck beyond that.

All the help on this would be greatly appreciated.

Thank You.

$\endgroup$
1
  • $\begingroup$ Indeed Strassen algorithm first divides a $4\times 4$ matrix in 4 blocks of $2\times 2$ matrices, see here. $\endgroup$
    – abx
    Mar 26, 2014 at 7:55

1 Answer 1

2
$\begingroup$

In fact, Strassen's algorithm process by induction as follows:

Strassen(A,B)

If $A$ and $B$ are small

 Perform the usual matrix multiplication;

else

Divide A and B into four parts $A_i$ and $B_j$ ($1 \leq i,j \leq 4$) respectively;
perform the 7 multiplications with Strassen($A_i$,$B_j$);
$\endgroup$

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