Explain Strassens matrix multiplication

Subject: Analysis Of Algorithm

Topic: Divide Aqnd Conquer

Difficulty: High

aoa(14) • 3.5k  views

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.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More