Strassen’s Algorithm.pptx

Strassen's Algorithm is a popular and efficient divide-and-conquer method for matrix multiplication. It was developed by Volker Strassen in 1969 and is particularly useful for multiplying large matrices. The algorithm reduces the number of basic multiplication operations required for matrix multiplication, resulting in improved computational efficiency compared to the traditional matrix multiplication algorithm, especially for large matrices.

1. Strassen’s Algorithm P R E S E N T A T I O N B Y , ABDOURAZAK H. GUEDI I M S C ( I T ) 1

2. content Introduction Procedure Formulas Pseudo code Conclusion 2

3. Introduction The Strassen algorithm , also known as Strassen's matrix multiplication algorithm . Strassen in 1969 which gives an overview that how we can find the multiplication of two matrix 2*2 dimension by the brute-force algorithm . But by using divide and conquer technique the overall complexity for multiplication of two matrices is reduced. This happens by decreasing the total number o f multiplication performed at the expenses of a slight increase in the number of addition. 3

4. For multiplying the two 2*2 dimension matrices Strassen's used some formulas in which there are eight multiplication and eighteen addition, subtraction , but in brute force algorithm, there is seven multiplication and four addition. The utility of Strassen's formula is shown by its asymptotic superiority when order n of matrix reaches infinity. Let us consider two matrices A and B , n*n dimension, where n is a power of two. It can be observed that we can contain four n/2*n/2 submatrices from A , B and their product C . C is the resultant matrix of A and B . Introduction 4

5. Procedure for Strassen matrix multiplication There are some procedures: 1. Divide a matrix of order of 2*2 recursively till we get the matrix of 2*2 . 2. Use the previous set of formulas to carry out 2*2 matrix multiplication. 3. In this seven multiplication and four additions, subtraction are performed. 4. Combine the result of two matrixes to find the final product or final matrix . 5

6. Formulas for Strassen mat r ix multiplication In Strassen's matrix multiplication there are seven multiplication and four addition, subtraction in total. D1 = (a11 + a22 ) . (b11 + b22) D2 = (a21 + a22). b11 D3 = (b12 – b22). a11 D4 = (b21 – b11). a22 D5 = (a11 + a12).b22 D6 = (a21 – a11 ) . ( b11 + b12 ) D7 = (a12 – a22 ) . ( b21 + b22) C11 = d1 + d4 – d5 + d7 C12 = d3 + d5 C21 = d2 + d4 C22 = d1 - d 2 + d 3 + d6 6

7. Pseudo code Algorithm Strassen(n, a, b, d) If n = threshold 2. C = a * b Else 3. Partition a into four sub matrices a11,a12,a21,a22. 4. Partition b into four sub matrices b11,b12,b21,b22. 5. Strassen ( n/2, a11 + a22, b11 + b22, d1) 7

8. 6. Strassen ( n/2, a21 + a22, b11, d2) 7. Strassen ( n/2, a11, b12 – b22, d3) 8. Strassen ( n/2, a22, b21 – b11, d4) 9. Strassen ( n/2, a11 + a12, b22, d5) 10. Strassen (n/2, a21 – a11, b11 + b 1 2 , d6) 11. Strassen (n/2, a12 – a22, b21 + b22, d7) 12. C = d1+d4-d5+d7 d3+d5 d2+d4 D 1 - d 2+ d 3+ d6 end if return (C) 8

9. Code: #include < stdio.h > int main () { int a [ 2 ][ 2 ], b [ 2 ][ 2 ], c [ 2 ][ 2 ], i , j ; int m1 , m2 , m3 , m4 , m5 , m6 , m7 ; printf ( " Enter the 4 elements of first matrix: " ) ; for ( i = ; i < 2 ; i ++) for ( j = ; j < 2 ; j ++) scan f ( " % d " , & a [ i ][ j ] ) ; printf ( " Enter the 4 elements of second matrix: " ) ; for ( i = ; i < 2 ; i ++) for ( j = ; j < 2 ; j ++) scanf ( " %d " ,& b [ i ][ j ]) ; printf ( " \n The first matrix is \n " ) ; for ( i = ; i < 2 ; i ++) { printf ( " \n " ) ; for ( j = ; j < 2 ; j ++) printf ( " %d \t " , a [ i ][ j ]) ; } printf ( " \n The second matrix is \n " ) ; 9

10. for ( i = ; i < 2 ; i ++) { printf ( " \n " ) ; for ( j = ; j < 2 ; j ++) printf ( " %d \t " , b [ i ][ j ]) ; } m1 = ( a [ ][ ] + a [ 1 ][ 1 ])*( b [ ][ ]+ b [ 1 ][ 1 ]) ; m2 = ( a [ 1 ][ ]+ a [ 1 ][ 1 ])* b [ ][ ] ; m3 = a [ ][ ]*( b [ ][ 1 ]- b [ 1 ][ 1 ]) ; m4 = a [ 1 ][ 1 ]*( b [ 1 ][ ]- b [ ][ ]) ; m5 = ( a [ ][ ]+ a [ ][ 1 ])* b [ 1 ][ 1 ] ; m6 = ( a [ 1 ][ ]- a [ ][ ])*( b [ ][ ]+ b [ ][ 1 ]) ; m7 = ( a [ ][ 1 ]- a [ 1 ][ 1 ])*( b [ 1 ][ ]+ b [ 1 ][ 1 ]) ; c [ ][ ]= m1 + m4 - m5 + m7 ; c [ ][ 1 ]= m3 + m5 ; c [ 1 ][ ]= m2 + m4 ; c [ 1 ][ 1 ]= m1 - m2 + m3 + m6 ; printf ( " \n After multiplication using \n " ) ; for ( i = ; i < 2 ; i ++) { printf ( " \n " ) ; for ( j = ; j < 2 ; j ++) printf ( " %d \t " , c [ i ][ j ]) ; } return ; } 6 2 5 1 Output: Complexity: The time complexity is O(N 2.8074 ) . 10

11. Conclusion The Strassen algorithm is a fast matrix multiplication algorithm that reduces the number of basic multiplications required for matrix multiplication. It reduced the number of multiplications from 8 (in the standard matrix multiplication) to 7, which results in a slightly lower overall time complexity. 11

12. Thank You 12