STRASSEN’S MATRIX MULTIPLICATION



STRASSEN’S MATRIX MULTIPLICATION USING DIVIDE AND CONQUER TECHNIQUE 

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
int **cremem(int);
int **readmat(int);
int **strassen(int **,int **,int);
int **addmat(int **,int **,int,int);
int **collect(int**,int**,int**,int**,int);
void dismat(int**,int);
void main()
{
int n,**a,**b,**ree;
clrscr();
cout<<"\n\t\tSTRASSEN'S MATRIX MULTIPLICATION USING D AND C";
cout<<"\n\t\t...............................";
cout<<"\nEnter the order of matrix:";
cin>>n;
cout<<"\nEnter the first matrix element:";
a=readmat(n);
cout<<"\nEnter the second matrix";
b=readmat(n);
ree=strassen(a,b,n);
cout<<"\nFirst matrix\n";
dismat(a,n);
cout<<"\nSecond matrix\n";
dismat(b,n);
cout<<"\nResult matrix\n";
dismat(ree,n);
free(ree);
getch();
}
int **readmat(int no)
{
int r,c,**mat;
mat=(int **)cremem(no+(no%2));
for(r=0;r<no;r++)
for(c=0;c<no;c++)
cin>>mat[r][c];
return mat;
}
int **cremem(int no)
{
int i,**a;
a=(int**)calloc(no,sizeof(int*));
for(i=0;i<no;i++)
a[i]=(int*)calloc(no,sizeof(int));
return a;
}

int **strassen(int **a,int **b,int no)
{
int r,c,**res,mv;
int **a11,**a12,**a21,**a22;
int **b11,**b12,**b21,**b22;
int **c11,**c12,**c21,**c22;
int **P,**Q,**R,**S;
int **T ,**U,**V,**temp;
if(no==1)
{
temp=(int **)cremem(no);
temp[0][0]=a[0][0]*b[0][0];
return temp;
}
no=no+(no%2);
mv=no/2;
a11=cremem(mv);
a12=cremem(mv);
a21=cremem(mv);
a22=cremem(mv);
b11=cremem(mv);
b12=cremem(mv);
b21=cremem(mv);
b22=cremem(mv);
for(r=0;r<mv;r++)
{
for(c=0;c<mv;c++)
{
a11[r][c]=a[r][c];
a21[r][c]=a[r+mv][c];
a12[r][c]=a[r][c+mv];
a22[r][c]=a[r+mv][c+mv];
b11[r][c]=b[r][c];
b21[r][c]=b[r+mv][c];
b12[r][c]=b[r][c+mv];
b22[r][c]=b[r+mv][c+mv];
}
}
P=strassen(addmat(a11,a22,mv,1),addmat(b11,b22,mv,1),mv);
Q=strassen(addmat(a21,a22,mv,1),b11,mv);
R=strassen(a11,addmat(b12,b22,mv,-1),mv);
S=strassen(a22,addmat(b21,b11,mv,-1),mv);
T=strassen(addmat(a11,a12,mv,1),b22,mv);
U=strassen(addmat(a21,a11,mv,-1),addmat(b11,b12,mv,1),mv);
V=strassen(addmat(a12,a22,mv,-1),addmat(b21,b22,mv,1),mv);
c11=addmat(addmat(addmat(P,S,mv,1),T,mv,-1),V,mv,1);
c12=addmat(R,T,mv,1);
c21=addmat(Q,S,mv,1);


c22=addmat(addmat(addmat(P,R,mv,1),Q,mv,-1),U,mv,1);
res=collect(c11,c12,c21,c22,no);
return res;
}
int **addmat(int**a,int **b,int no,int oper)
{
int **res,r,c;
res=(int **)cremem(no);
for(r=0;r<no;r++)
for(c=0;c<no;c++)
res[r][c]=a[r][c]+oper*b[r][c];
return res;
}
int **collect(int**c11,int**c12,int**c21,int **c22,int no)
{
int **res,r,c;
res=(int **)cremem(no);
for(r=0;r<(no/2);r++)
for(c=0;c<(no/2);c++)
{
res[r][c]=c11[r][c];
res[r+(no/2)][c]=c21[r][c];
res[r][c+(no/2)]=c12[r][c];
res[r+(no/2)][c+(no/2)]=c22[r][c];
}
return res;
}
void dismat(int**d,int no)
{
int r,c;
for(r=0;r<no;r++)
for(c=0;c<no;c++)
cout<<"\t"<<d[r][c];
cout<<"\n";
}


 

OUTPUT:          
                       

                STRASSEN'S MATRIX MULTIPLICATION USING D AND C
                ...............................
Enter the order of matrix:3

Enter the first matrix element:
1  2  3
4  5  6
7  8  9

Enter the second matrix
1  2  1
2  1  2
1  2  1

Comments

Post a Comment

Popular posts from this blog

TRAVELING SALESMAN USING BRANCH AND BOUND TECHNIQUE

Image
The Traveling Salesman Problem (TSP) is a classic problem in computer science and optimization theory. The problem is defined as follows: given a set of cities and the distances between them, find the shortest possible path that visits each city exactly once and returns to the starting city. The Branch and Bound technique is an algorithmic paradigm for solving combinatorial optimization problems. The basic idea is to explore the search space by dividing it into smaller subproblems, and then pruning branches of the search tree that can be shown to lead to suboptimal solutions. The branch and bound algorithm for the TSP works by starting with an initial lower bound on the length of the optimal tour, and then exploring the search space by systematically building up partial tours and computing lower bounds on their completion. Sample C code for solving the Traveling Salesman Problem(TSP) using the branch and bound technique: #include <stdio.h> #include <stdlib.h> #include &
Read more

BOOKS DETAILS USING C STRUCTURE

              To write a c program to create a collection of books using array of structure and performs the following operatons. (i)                  Searching a book with title and author name. (ii)                Sort the book based on title. /*BOOKS DETAILS*/ #include<stdio.h> #include<conio.h> #include<string.h> struct books { char book[20]; char author[20]; int price; }; int main() { int i,ch,j,n,flag=1; struct books l[10]; struct books t[1]; char sbook[20],saut[20]; clrscr(); do{ clrscr(); printf("\n\t\tBOOK LIST\n\nMAIN MENU\n\n"); printf("\n1.creation\n2.search by title & author\n"); printf("3.sort by title\n4.exit\n"); printf("\nEnter your choice:"); scanf("%d",&ch); switch(ch) { case 1: clrscr(); printf("\nEnter number of booklist:"); scanf("%d",&n); for(i=1;i<=n;i+
Read more

TRAVELING SALESMAN USING BRANCH AND BOUND TECHNIQUE

TRAVELING SALESMAN USING BRANCH AND     BOUND TECHNIQUE  #include<iostream.h> #include<conio.h> int main() { int i,j,k,n,min,g[20][20],c[20][20],s,s1[20][1],s2,lb; clrscr(); cout<<"\n TRAVELLING SALESMAN PROBLEM"; cout<<"\n Input number of cities:"; cin>>n; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { c[i][j]=0; }} for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j) continue; else{ cout<<"input"<<i<<"to"<<j<<"cost:"; cin>>c[i][j]; } } } for(i=2;i<=n;i++) { g[i][0]=c[i][1]; } for(i=2;i<=n;i++) { for(j=2;j<=n;j++) { if(i!=j) g[i][j]=c[i][j]+g[j][0]; } } for(i=2;i<=n;i++) { for(j=2;j<=n;j++) { if(i!=j) break; } } for(k=2;k<=n;k++){ if(i!=k && j!=k){ if((c[i][j]+g[i][k])<(c[i][k]+g[k][j])) { g[i][j]=c[i][j]+g[j][k]; s1[i][j]=j; } else { g[i][1]=c[i][k]+g[k][j];
Read more