Explain Strassens matrix multiplication

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++)
  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.

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more