Strassen’s matrix multiplication

1. Let A and B be two nn matrices, that is, each having n rows and n columns. If C=AB, then the product matricx C will also have n rows and n columns.

2. An element C[i, j] can now be found using the formula

   $$C [i, j] = \sum_{k=0}^{n-1}A[i,k]*B[k,j] $$

3. The method of multiplying two matrices is known as the classic matrix multiplication method. Using the above formula, we may write the following statements:

   for( i=0; i < n; i++)
   
   for( j=0; j<n; j++)
   
   {
   
       C[i] [j] =0;
   
       for( k=0;k<n;k++)
   
       C[i][j]=c[i][j]+a[i][k]*b[k][j];
   
   }
   

4. It can be easily verified that the complexity of the method is $O (n^3)$.

5. Strassen’s matrix multiplication can be used only when n is a power of 2i.e. $n=2^k$. If n is not a power of 2 then enough rows and columns of zeros can be added to both A and B so that the resulting dimension are a power of 2.

6. In this method matrix A and B are splitted into 4 squares sub-matrices where each sub-matrices has dimension of n/2. Now the product is found as shown:

   $1\begin{matrix} A_{11}&A_{12} \\ A_{21}&A_{22} 1 \\ \end{matrix}1$ $\hspace{0.5cm}$ $1\begin{matrix} B_{11}&B_{12} \\ B_{21}&B_{22} 1 \\ \end{matrix}1$ $\hspace{0.5cm}$ $\begin{matrix} C_{11}&C_{12} \\ C_{21}&C_{22} 1 \\ \end{matrix}1$

   $P = (A_{11}+A_{22}) ( B_{11}+B_{22}) \\ Q = (A_{21}+A_{22}) B_{11} \\ R = A_{11}( B_{12}-B_{22})$

   $S= A_{22}( B_{21}-B_{11})$

   $T= (A_{11}+A_{12})B_{22} \\ U= (A_{21}-A_{11}) ( B_{11}+B_{22}) \\ V= (A_{12}-A_{22}) ( B_{21}+B_{22}) \\ C_{11} = P+S-T+V \\ C_{12} = R+T \\ C_{21} = Q+S \\ C_{22} P+R-Q+U$

   It is observed that all c [i, j] can be calculated using a total of 7 multiplications and 18 additions or subtractions.

7. Consider the following example:

   $\begin{matrix} 1&2 \\ 4&5 \\ \end{matrix}$ $\hspace{0.5cm}$ * $\begin{matrix} 6&8 \\ 7&9 \\ \end{matrix}$ $\hspace{0.5cm}$ $\begin{matrix} C_{11}&C_{12} \\ C_{21}&C_{22} 1 \\ \end{matrix}1$

   Now we want to find C12, this can be done as shown:-

   R=1*(8-9) =-1,

   T= (1+2) *9=27,

   C_12 = -1+27=26

   Similarly, C_21 can be found as shown

   Q= (4+5) *6=54

   S= 5*(7-6) =5

   C_21 = 54+5 =59

8. It is not necessary that n should be always 2. If n>2 then the same formula can be used but now it will be done recursively. The same formula will be continuously applied on smaller sized matrices till n gets reduced to 2. When n=2, this will be terminating condition of recursion and now multiplication is done directly.