Strassen’s Algorithm and matrix multiplication

this is a part of the matrix algorithm

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