Question

A Strasen-like method for multiplying a 2x2 matrix
Write the algorithm for (brute force, divide and conquer or karatsuba).
Calculate the complexity. See all possible situations.

Answer 1

Hi

Algorithm:

begin 
        If n = threshold then compute
                C = a * b is a conventional matrix.
        Else
                Partition a into four sub matrices  a11, a12, a21, a22.
                Partition b into four sub matrices b11, b12, b21, b22.
                Strassen ( n/2, a11 + a22, b11 + b22, d1)
                Strassen ( n/2, a21 + a22, b11, d2)
                Strassen ( n/2, a11, b12 – b22, d3)
                Strassen ( n/2, a22, b21 – b11, d4)
                Strassen ( n/2, a11 + a12, b22, d5)
                Strassen (n/2, a21 – a11, b11 + b22, d6)
                Strassen (n/2, a12 – a22, b21 + b22, d7)

                C = d1+d4-d5+d7     d3+d5
                d2+d4           d1+d3-d2-d6  
                
        end if
        
        return (C)
end.

Addition and Subtraction of two matrices takes O(N²) time. So time complexity can be written as

T(N) = 7T(N/2) +  O(N2)

From Master's Theorem, time complexity of above method is 
O(NLog7) which is approximately O(N2.8074)

Program:

#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=0;i<2;i++)
       for(j=0;j<2;j++)
           scanf("%d",&a[i][j]);

   printf("Enter the 4 elements of second matrix: ");
   for(i=0;i<2;i++)
       for(j=0;j<2;j++)
           scanf("%d",&b[i][j]);

   printf("\nThe first matrix is\n");
   for(i=0;i<2;i++)
   {
       printf("\n");
       for(j=0;j<2;j++)
           printf("%d\t",a[i][j]);
   }

   printf("\nThe second matrix is\n");
   for(i=0;i<2;i++)
   {
       printf("\n");
       for(j=0;j<2;j++)
           printf("%d\t",b[i][j]);
   }

   m1= (a[0][0] + a[1][1])*(b[0][0]+b[1][1]);
   m2= (a[1][0]+a[1][1])*b[0][0];
   m3= a[0][0]*(b[0][1]-b[1][1]);
   m4= a[1][1]*(b[1][0]-b[0][0]);
   m5= (a[0][0]+a[0][1])*b[1][1];
   m6= (a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
   m7= (a[0][1]-a[1][1])*(b[1][0]+b[1][1]);

   c[0][0]=m1+m4-m5+m7;
   c[0][1]=m3+m5;
   c[1][0]=m2+m4;
   c[1][1]=m1-m2+m3+m6;

   printf("\nAfter multiplication using \n");
   for(i=0;i<2;i++)
   {
       printf("\n");
       for(j=0;j<2;j++)
           printf("%d\t",c[i][j]);
   }

   printf("\n");
   return 0;
}

Screenshot: