Strassen_s Matrix Multiplication Fifth SemesSemester

Strassen mult

1. Department of Computer Science & Engineering Subject: Analysis Design of Algorithm [CS402] Prestige Institute of Engineering, Management & Research, Indore Lecture No. Topic : : Strassen's Matrix Multiplication By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore

2. Prerequisite How two Matrices are multiplied with each other? Code for Matrices multiplication (normal code as per point .1 in this slide). Complexity of code of Matrices multiplication Is there any better way to solve this problem Yes Divide and Conquer If problem is large break the problem into smaller subproblems then solve those subproblems and combine those subproblems and get the final result. When we say the problem is large then we must know that what is a small problem (means sub-problem of problem)---base case

3. Matrix Multiplication(1) Matrix multiplication is a binary operation whose output is also a matrix when two matrices are multiplied. In general, matrix multiplication, unlike arithmetic multiplication, is not commutative, which means the multiplication of matrix A and B, given as AB, cannot be equal to BA, i.e., AB ≠ BA. It is also known as dot product.

4. Matrix Multiplication Rules If two matrices are compatible i.e. no. of columns in first matrix is equal to no. or rows in second matrix. The resultant matrix has row equal to rows present in first matrix and no. of columns present in second matrix.

5. Code for Matrix Multiplication for(i=0; i<n:i++) { for(j=0; i<n:j++) { C[i,j] = 0 for(k=o; k<n:i++) { C[i,j] += A[i,k] * B[k,j] } } } Complexity of this code is O(n^3)

6. Divide And Conquer (DAC) for Matrix Multiplication If the problem is such that A and B both are of dimensions 2x2 then we say problem is a small problem and we solve using normal strategy . But if problem is bigger like 4x4 & 4x4 , 8x8 & 8x8 etc then we use DAC for solution . We need to define a small problem before applying the DAC strategy

7. 2x2 & 2x2 Matrix Multiplication Define a small problem We can directly use this formula for 2x2 * 2x2 We are not using 3 loops but directly using this formula. All the 4 statements are taking constant time so let’s say 4 units(constant time).

8. Defining small problem for Matrix Multiplication If the size of the problem is less than or equal to 2 then problem is small size of the problem <= 2 What if the size of the problem > 2 We assume that matrices are having dimensions powers of 2 only like 2^2, 2^3, 2^8 etc or 4x4 & 4x4 , 8x8 & 8x8 etc. If the problem is not in power of 2 then fill the matrix with 0s and make it in the power of 2. A=[a 11 ] B=[b 11 ] C= [a 11 * b 11 ]

9. 4x4 & 4x4 Matrix Multiplication The matrix must be divided by 2. If we will divide the matrices by 2 then we get 4 matrices of size 2x2 from first and similarly from second matrix also. Now the matrices are like followings [A 11 ] [A 12 ] [B 11 ] [B 12 ] [A 21 ] [A 22 ] [B 21 ] [B 22 ] Consider this matrix as A 11 (means single element) Consider this matrix as A 12 (means single element)

10. Algorithm Matrix Multiplication Algorithm MM(A,B,n): if(n<=2) c= < The four Formulas we have discussed in previous slide >} Else{ mid= n/2 MM(A 11 , B 11 , n/2)+ MM(A 12 , B 21 , n/2) MM(A 11 , B 12 , n/2)+ MM(A 12 , B 22 , n/2) MM(A 21 , B 11 , n/2)+ MM(A 22 , B 21 , n/2) MM(A 21 , B 12 , n/2)+ MM(A 12 , B 22 , n/2) }

11. Time Complexity Matrix Multiplication T(n) = { Division is n/2 and in algorithm it calling the algorithm MM 8 times Due to matrix addition operation (use to combine the two recursive calls in steps 5,6,7,8 of algorithm). It will take n 2 time to add two matrices of nxn size 1 n<=2 8T(n/2)+n 2 n>2 Apply Master Theorem on this T(n) = 8T(n/2)+n 2 T(n)= 𝝝(n 3 )

12. Iterative or Recursive for Matrix Multiplication? Its time complexity is n 3 using both the approaches i.e. iterative or recursive but in recursive internally, recursive is taking more memory in terms of Stack. In terms of space, it is better to use 3 loops or iterative method. Is there any chance to reduce the complexity?

13. Strassen’s Matrix Multiplication(1) The major operation in Matrix Multiplication is multiple operation so Strassen’s Matrix Multiplication has reduced the multiplication operation. But addition and Subtraction have increased.

14. Strassen’s Matrix Multiplication(2) This is previous formula [A 11 ] [A 12 ] [B 11 ] [B 12 ] [A 21 ] [A 22 ] [B 21 ] [B 22 ]

15. Time Complexity Strassen’s Matrix Multiplication T(n) = { Log 2 7 = 2.81 and k=2 (as per master theorem) O(n 2.81 ) Strassen’s Multiplication has reduced the complexity by few points. 1 n<=2 7T(n/2)+n 2 n>2

16. Write a program to multiply two matrices of order 2x2 using Strassen’s Matrix Multiplication