ANALYSIS DESIGN OF ALGORITHM (ADA) | STRASSEN'S MATRIX MULTIPLICATION

📌Highlights:

Hi Friends ! In this post I am going to explain about Strassen's Matrix Multiplication using Divide And Conquer Strategy. Also explain the concept of Simple Matrix Multiplication. I also explain what is the benefit of  Strassen's Matrix Multiplication over Simple Matrix Multiplication using Divide And Conquer Strategy. What is the formula used to solve Strassen's Matrix Multiplication.

Strassen's Matrix Multiplication  

is basically used to improve the process of simple matrix multiplication.For this 

👉 How simple matrix multiplication done normally. 

👉How divide and conquer strategy is apply to solve matrix multiplication problem. 

👉What Strassen's Matrix Multiplication had done to improve matrix multiplication using divide and conquer strategy ?

Let we first understand Normal matrix multiplication.

Here we take matrix of  (2X2). Now multiply both matrix A and matrix B , we get third matrix C of (2x2).

Method of multiplication are:

C11 = a11 * b11 + a12 * b21

C12 = a11 * b12 + a12 * b22

C21 = a21 * b11 + a22 * b22

C12  = a21 * b12 + a22 * b22

We can also say that these are the four formulas for finding third resulting matrix i.e C.

Now Let we understand the logic and how write it:

 // Multiplying first A and second B matrices and storing it in third matrix C

   for (int i = 0; i < n; ++i) 

{

      for (int j = 0; j < n; ++j)

     {

         C[i, j] =  0;

         for (int k = 0; k < n; k++) 

        {

            C[i,j] += A[i,k] * B[k,j];

        }

    }

}

This is a basic method to multiply two matrix but it is easy when matrix are of small size like (2X2). But if the size of matrix become big like (4X4, 6X6, 8X8 etc.) than this method is not appropriate so here by using Divide and Conquer strategy we can solve easily.

Now the Algorithm will be:

Algorithm MatrixMult(A,B,N)

STEP 1: CHECK IF (N <=2) THEN

STEP 2: APPLY FOUR FORMULAS

            C11 = a11 * b11 + a12 * b21

            C12 = a11 * b12 + a12 * b22

            C21 = a21 * b11 + a22 * b21

            C12  = a21 * b12 + a22 * b22

STEP 3: ELSE

STEP 3.1: MID = N / 2  //Find MID

STEP 3.2: CALL MatrixMult FUNCTION RECURSIVELY

                MatrixMult (A11,B11,N/2) + MatrixMult (A12,B21,N/2)

                MatrixMult (A11,B12,N/2) + MatrixMult (A12,B22,N/2)

                MatrixMult (A21,B11,N/2) + MatrixMult (A22,B21,N/2)

                MatrixMult (A21,B12,N/2) + MatrixMult (A22,B22,N/2)

STEP 3.3: END ELSE

STEP 4: END IF

Now Let we understand if the size of matrix is big size than how we apply divide and conquer strategy.

Suppose we have matrix of (4 x 4)

Now we can say that this problem is large. So for solving such a large problem we need to divide this problem into sub problems and than combine those sub problems.

Let we do it

Divide (4 x 4) dimension by 2 such as (4 x 4) /2 than the whole matrix is   is divide into four parts such as (4/2 x 4/2) it looks :

Now we get four matrix such as:

Now the above matrix is in the form of (2 x 2 ) so it can easy to solve. Apply the above algorithm on it. But it will take more time and space to solve such a problem by this method.

The recurrence relation for this is:

Using Master’s theorem to solve the above equation where:

a=8, b=2 and f(n)= n²

thus,

from this, we infer that which equals to 3 and n^k = n²

Using of master’s theorem, we get: O(n³)

Even after using divide and conquer to solve the 4x4 matrix multiplication problem, we find out that the time complexity remains the same. Even using recursion for the divide and conquer approach, the time complexity is O(n³), which is the same as using three nested for loops. The divide and conquer approach is recursive, thus it uses stack and ends up using even more space.

Here if we apply strassen's concept then the process become faster than above method. So let we understand strassen's method.

In above method or algorithm four formulas are used in the form of recursive functions such as 

STEP 3.2: CALL MatrixMult FUNCTION RECURSIVELY

                MatrixMult (A11,B11,N/2) + MatrixMult (A12,B21,N/2)

                MatrixMult (A11,B12,N/2) + MatrixMult (A12,B22,N/2)

                MatrixMult (A21,B11,N/2) + MatrixMult (A22,B21,N/2)

                MatrixMult (A21,B12,N/2) + MatrixMult (A22,B22,N/2)

So here total eight multiplication had done. If we apply strassen's approach then it will reduce the number of multiplications and than the algorithm become fast.

So instead of these four formulas strassen's given some different formulas such as:

We use the formulae below made by Strassen's to get the C matrix:

Using these seven formulae, we insert them into the C matrix by:

EXAMPLE 1:

Multiply the matrix using strassen's Matrix Multiplication.

A11 =1 ,   A12 =3 ,   A21 = 7 ,   A22 = 5    

B11 = 6 ,   B12 = 7 ,   B21 = 3 ,   B22 = 8

APPLY STRASSEN'S FORMULA WE GET

P = (1+5)(6+8) = 6* 14 =84

Q = 6 (7+5) = 6*12 = 72

R = 1 (7-8) = -1

S = 5 (3-6) = -15

T = 8 (1+3) = 32

U = (6+7) (7-1) = 13 * 6 =78

V = (3+8)(3-5) = 11 * -2 = -22

NOW,

C11  = P + S - T + V

        = 84 + (-15) - 32 + (-22)

        = 15

C12 = R + T

        = -1 + 32

        = 31

C21 = Q + S

        = 72 + (-15)

        = 57

C22 = P + R - Q + U

        = 84 + (-1) - 72 + 78

        = 89

SO  MATRIX C WILL BE:

EXAMPLE 2:

Multiply the matrix using strassen's Matrix Multiplication.

P = (A11 + A22)(B11 + B22)

P = (2 + 2)(1 + 2)

P = 12

Q = B11 (A21 + A22)

Q = 1(3 + 2)

Q = 5

R = A11(B12 - B22)

R = 2(2 - 2)

R = 2*0

R = 0

S = A22 (B21 - B11)

S = 2(3 - 1)

S = 4

T = B22 (A11 + A12)

T = 2 (2 + 4)

T = 2*6

T = 12

U = (B11 + B12)(A21 - A11)

U = (1 + 2)(3 - 2)

U = 3 * 1

U = 3

V = (B21 + B22)(A12 - A22)

V = (3 + 2) (4 - 2)

V = 5 * 2

V = 10

C11 = P + S - T + V

C11 = 12 + 4 - 12 + 10

C11 = 14

C12 = R + T

C12 = 0 + 12

C12 = 12

C21 = Q + S

C21 = 5 + 4

C21 = 9

C22 = P + R - Q + U

C22 = 12 + 0 - 5 + 3

C22 = 10

FINALLY WE GET

📌Friends ! this is all about Strassen's Matrix Multiplication. So I hope this post is helpful for you to understand the method of strassen's Matrix Multiplication using Divide and Conquer Strategy. We will meet in new post till continue reading...