Question: Explain Strassens matrix multiplication

Subject: Analysis Of Algorithm

Topic: Divide Aqnd Conquer

Difficulty: High

aoa(14) • 3.2k views
modified 21 months ago by gravatar for awari.swati831 awari.swati831250 written 3.3 years ago by gravatar for satishmanje93 satishmanje9320

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.

written 3.3 years ago by gravatar for satishmanje93 satishmanje9320
Please log in to add an answer.