Question: Explain Strassens matrix multiplication
0

Subject: Analysis Of Algorithm

Topic: Divide Aqnd Conquer

Difficulty: High

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

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.

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