Sparse Matrix Operations in C
Represent Sparse Matrix using array and perform Matrix Addition, Simple and Fast Transpose.
Polynomial representation using array, Concept of Sparse Matrix, it’s usage & representation using arrays, Algorithms for sparse matrix operations like addition, simple transpose, fast transpose & multiplication
|
1 2 |
<br/><br/> #define max 50 <br/> #include <br/> #include <br/> int input(int as[][3]); <br/> void display(int*,int,int); <br/> void display1(int[][3]); <br/> void sp(int *,int [][3],int,int); <br/> void add(int[][3],int[][3],int[][3]); <br/> void sub(int[][3],int[][3],int[][3]); <br/> void trans(int [][3],int [][3]); <br/> void ftrans(int[][3],int [][3]); <br/> void mul(int[][3],int [][3],int[][3]); <br/> void main() <br/> { <br/> int as[max][3],bs[max][3],r[max][3],ch,ch1; <br/> as[0][2]=0; <br/> bs[0][2]=0 ; <br/> do <br/> { <br/> clrscr(); <br/> printf("Enter your choice to performe sparse matrix menuplation"); <br/> printf("\n1.Input matrix\n2.Display Sparse matrix"); <br/> printf("\n3.Addition of two sparse matrix\n"); <br/> printf("4.Subtraction of two sparse matrix"); <br/> printf("\n5.Multiplecation of two sparse matrix"); <br/> printf("\n6.Transpose of matrix\n7.Fast transpose of matrix"); <br/> printf("\n8.Exit"); <br/> scanf("%d",&ch); <br/> switch(ch) <br/> { <br/> case 1: <br/> do <br/> { <br/> clrscr(); <br/> printf("\nEnter your choice\n"); <br/> printf("1.Matrix 1\n2.Matrix 2\n3.return"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1 : <br/> clrscr(); <br/> input(as); <br/> break; <br/> case 2 : <br/> clrscr(); <br/> input(bs); <br/> break; <br/> case 3: <br/> break; <br/> default: <br/> printf("\nInvalid choice\n"); <br/> getch(); <br/> } <br/> }while(ch1!=3); <br/> break; <br/> case 2: <br/> do <br/> { <br/> clrscr(); <br/> printf("\nEnter your choice to display\n"); <br/> printf("1.Matrix 1\n2.Matrix 2\n3.return"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1 : <br/> clrscr(); <br/> if(as[0][2]==0) <br/> { <br/> printf("First enter the matrix1\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("Sparse matrix 1=\n"); <br/> display1(as); <br/> getch(); <br/> } <br/> break; <br/> case 2 : <br/> clrscr(); <br/> if(bs[0][2]==0) <br/> { <br/> printf("First enter the matrix2\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("Sparse matrix 2=\n"); <br/> display1(bs); <br/> getch(); <br/> } <br/> break; <br/> case 3: <br/> break; <br/> default: <br/> printf("\nInvalid choice\n"); <br/> getch(); <br/> } <br/> }while(ch1!=3); <br/> break; <br/> case 3: <br/> clrscr(); <br/> if(as[0][2]==0||bs[0][2]==0) <br/> { <br/> printf("First enter both matrices\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> add(as,bs,r); <br/> printf("\nSPARSE ADDITION OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 4: <br/> do <br/> { <br/> clrscr(); <br/> printf("\nEnter your choice to Sparse subtraction"); <br/> printf("\n1.MAT A- MAT B\n2.MAT B-MAT A\n3.RETURN"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> clrscr(); <br/> if(as[0][2]==0||bs[0][2]==0) <br/> { <br/> printf("First enter both matrices\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> sub(as,bs,r); <br/> printf("\nSPARSE SUBTRACTION OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 2: <br/> clrscr(); <br/> if(as[0][2]==0||bs[0][2]==0) <br/> { <br/> printf("First enter both matrices\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> sub(bs,as,r); <br/> printf("\nSPARSE SUBTRACTION OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 3: <br/> break; <br/> } <br/> }while(ch1!=3); <br/> break; <br/> case 5: <br/> do <br/> { <br/> clrscr(); <br/> printf("\nEnter your choice to Sparse subtraction"); <br/> printf("\n1.MAT A* MAT B\n2.MAT B*MAT A\n3.RETURN"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> clrscr(); <br/> if(as[0][2]==0||bs[0][2]==0) <br/> { <br/> printf("First enter both matrices\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> mul(as,bs,r); <br/> printf("\nSPARSE MULTIPLECATION OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 2: <br/> clrscr(); <br/> if(as[0][2]==0||bs[0][2]==0) <br/> { <br/> printf("First enter both matrices\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> mul(bs,as,r); <br/> printf("\nSPARSE MULTIPLECATION OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 3: <br/> break; <br/> } <br/> }while(ch1!=3); <br/> break; <br/> case 6: <br/> do <br/> { <br/> clrscr(); <br/> printf("\nEnter your choice to Sparse Simple transpose"); <br/> printf("\n1.MAT A\n2.MAT B\n3.RETURN"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> clrscr(); <br/> if(as[0][2]==0) <br/> { <br/> printf("First enter the matrix1\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> trans(as,r); <br/> printf("\nSPARSE SIMPLE TRANSPOSE OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 2: <br/> clrscr(); <br/> if(bs[0][2]==0) <br/> { <br/> printf("First enter the matrix2\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> trans(bs,r); <br/> printf("\nSPARSE SIMPLE TRANSPOSE OF TWO MATRIX-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 3: <br/> break; <br/> } <br/> }while(ch1!=3); <br/> break; <br/> case 7: <br/> clrscr(); <br/> do <br/> { <br/> clrscr(); <br/> printf("\nEnter your choice to Sparse Fast transpose"); <br/> printf("\n1.MAT A\n2.MAT B\n3.RETURN"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> clrscr(); <br/> if(as[0][2]==0) <br/> { <br/> printf("First enter the matrix1\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX A-\n"); <br/> display1(as); <br/> ftrans(as,r); <br/> printf("\nSPARSE FAST TRANSPOSE OF MATRIX A-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 2: <br/> clrscr(); <br/> if(bs[0][2]==0) <br/> { <br/> printf("First enter the matrix2\n"); <br/> getch(); <br/> } <br/> else <br/> { <br/> printf("SPARSE MATRIX B-\n"); <br/> display1(bs); <br/> ftrans(bs,r); <br/> printf("\nSPARSE FAST TRANSPOSE OF MATRIX B-\n"); <br/> display1(r); <br/> getch(); <br/> } <br/> break; <br/> case 3: <br/> break; <br/> } <br/> }while(ch1!=3); <br/> break; <br/> ca se 8: <br/> break; <br/> default: <br/> printf("\nINVALID CHOICE"); <br/> getch(); <br/> } <br/> }while(ch!=8); <br/> getch(); <br/> } <br/> int input(int as[][3]) <br/> { <br/> int *mat,*r,*c,i,j,n1; <br/> printf("Enter no. of rows <50:\n"); <br/> scanf("%d",r); <br/> printf("Enter no. of colums <50:\n"); <br/> scanf("%d",c); <br/> if(*r>max || *c>max) <br/> { <br/> printf("Error : \nSize of matrix is not is range."); <br/> getch(); <br/> return(0); <br/> } <br/> else <br/> { <br/> mat=(int*)calloc(*r,(*c)*(sizeof(int))); <br/> printf("Enter elements of matrix \n"); <br/> for(i=0;i<*r;i++) <br/> { <br/> for(j=0;j<*c;j++) <br/> { <br/> scanf("%d",(mat+(i*(*c))+j)); <br/> } <br/> } <br/> } <br/> printf("Matrix is -\n"); <br/> display(mat,*r,*c); <br/> printf("\nSparse form of matrix is-\n"); <br/> sp(mat,as,*r,*c); <br/> free(mat); <br/> display1(as); <br/> printf("\n"); <br/> getch(); <br/> return(0); <br/> } <br/> void display(int *mat,int r,int c) <br/> { <br/> int i,j; <br/> for(i=0;i<r;i++) <br=""> { <br/> for(j=0;j<c;j++) <br=""> { <br/> printf("%d\t",*(mat+(i*c)+j)); <br/> } <br/> printf("\n"); <br/> } <br/> } <br/> void sp(int *mat,int as[][3], int r,int c) <br/> { <br/> int i,j,n=0; <br/> as[0][0]=r; <br/> as[0][1]=c; <br/> for(i=0;i<r;i++) <br=""> { <br/> for(j=0;j<c;j++) <br=""> { <br/> if(*(mat+(i*c)+j)!=0) <br/> { <br/> n++; <br/> as[n][0]=i; <br/> as[n][1]=j; <br/> as[n][2]=*(mat+(i*c)+j); <br/> } <br/> } <br/> } <br/> as[0][2]=n; <br/> } <br/> void display1(int mat[][3]) <br/> { <br/> int i; <br/> for(i=0;i<=mat[0][2];i++) <br/> printf("%d\t%d\t%d\n",mat[i][0],mat[i][1],mat[i][2]); <br/> } <br/> void add(int as[][3],int bs[][3],int r[][3]) <br/> { <br/> int i=1,j=1,k=1; <br/> if(as[0][0]!=bs[0][0] || as[0][1]!=bs[0][1]) <br/> { <br/> printf("\nRank of matrices is not Suitable"); <br/> return; <br/> } <br/> else <br/> { <br/> r[0][0]=as[0][0]; <br/> r[0][1]=as[0][1]; <br/> while(i<=as[0][2] && j<=bs[0][2]) <br/> { <br/> if(as[i][0]==bs[j][0] && as[i][1]==bs[j][1]) <br/> { <br/> r[k][2]=as[i][2]+bs[j][2]; <br/> if(r[k][2]!=0) <br/> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> k++; <br/> } <br/> j++;i++; <br/> } <br/> else <br/> { <br/> if(as[i][0]<bs[j][0]) <br=""> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> r[k][2]=as[i][2]; <br/> i++;k++; <br/> } <br/> else <br/> { <br/> if(as[i][0]==bs[j][0]) <br/> { <br/> if(as[i][1]<bs[j][1]) <br=""> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> r[k][2]=as[i][2]; <br/> i++;k++; <br/> } <br/> else <br/> { <br/> r[k][0]=bs[j][0]; <br/> r[k][1]=bs[j][1]; <br/> r[k][2]=bs[j][2]; <br/> j++;k++; <br/> } <br/> } <br/> else <br/> { <br/> r[k][0]=bs[j][0]; <br/> r[k][1]=bs[j][1]; <br/> r[k][2]=bs[j][2]; <br/> j++;k++; <br/> } <br/> } <br/> } <br/> } <br/> while(i<=as[0][2]) <br/> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> r[k][2]=as[i][2]; <br/> i++;k++; <br/> } <br/> while(j<=bs[0][2]) <br/> { <br/> r[k][0]=bs[j][0]; <br/> r[k][1]=bs[j][1]; <br/> r[k][2]=bs[j][2]; <br/> j++;k++; <br/> } <br/> } <br/> r[0][2]=k-1; <br/> } <br/> void sub(int as[][3],int bs[][3],int r[][3]) <br/> { <br/> int i=1,j=1,k=1; <br/> if(as[0][0]!=bs[0][0] || as[0][1]!=bs[0][1]) <br/> { <br/> printf("\nRank of matrices is not Suitable"); <br/> return; <br/> } <br/> else <br/> { <br/> r[0][0]=as[0][0]; <br/> r[0][1]=as[0][1]; <br/> while(i<=as[0][2] && j<=bs[0][2]) <br/> { <br/> if(as[i][0]==bs[j][0] && as[i][1]==bs[j][1]) <br/> { <br/> r[k][2]=as[i][2]-bs[j][2]; <br/> if(r[k][2]!=0) <br/> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> k++; <br/> } <br/> j++;i++; <br/> } <br/> else <br/> { <br/> if(as[i][0]<bs[j][0]) <br=""> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> r[k][2]=as[i][2]; <br/> i++;k++; <br/> } <br/> else <br/> { <br/> if(as[i][0]==bs[j][0]) <br/> { <br/> if(as[i][1]<bs[j][1]) <br=""> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> r[k][2]=as[i][2]; <br/> i++;k++; <br/> } <br/> else <br/> { <br/> r[k][0]=bs[j][0]; <br/> r[k][1]=bs[j][1]; <br/> r[k][2]=-bs[j][2]; <br/> j++;k++; <br/> } <br/> } <br/> else <br/> { <br/> r[k][0]=bs[j][0]; <br/> r[k][1]=bs[j][1]; <br/> r[k][2]=-bs[j][2]; <br/> j++;k++; <br/> } <br/> } <br/> } <br/> } <br/> while(i<=as[0][2]) <br/> { <br/> r[k][0]=as[i][0]; <br/> r[k][1]=as[i][1]; <br/> r[k][2]=as[i][2]; <br/> i++;k++; <br/> } <br/> while(j<=bs[0][2]) <br/> { <br/> r[k][0]=bs[j][0]; <br/> r[k][1]=bs[j][1]; <br/> r[k][2]=-bs[j][2]; <br/> j++;k++; <br/> } <br/> } <br/> r[0][2]=k-1; <br/> } <br/> void trans(int as[][3],int r[][3]) <br/> { <br/> int i,j,k=1; <br/> r[0][0]=as[0][1]; <br/> r[0][1]=as[0][0]; <br/> r[0][2]=as[0][2]; <br/> for(i=0;i<as[0][1];i++) <br=""> { <br/> for(j=1;j<=as[0][2];j++) <br/> { <br/> if(as[j][1]==i) <br/> { <br/> r[k][0]=as[j][1]; <br/> r[k][1]=as[j][0]; <br/> r[k][2]=as[j][2]; <br/> k++; <br/> } <br/> } <br/> } <br/> } <br/> void ftrans(int as[][3],int r[][3]) <br/> { <br/> int i,j,count[max],pos[max],rp; <br/> r[0][0]=as[0][1]; <br/> r[0][1]=as[0][0]; <br/> r[0][2]=as[0][2]; <br/> for(i=0;i<as[0][1];i++) <br=""> count[i]=0; <br/> for(i=1;i<=as[i][2];i++) <br/> count[as[i][1]]++; <br/> pos[0]=1; <br/> for(i=0;i<(as[0][1]-1);i++) <br/> pos[i+1]=pos[i]+count[i]; <br/> for(i=1;i<=as[0][2];i++) <br/> { <br/> rp=pos[as[i][1]]++; <br/> r[rp][0]=as[i][1]; <br/> r[rp][1]=as[i][0]; <br/> r[rp][2]=as[i][2]; <br/> } <br/> } <br/> void mul(int as[][3],int bs[][3],int r[][3]) <br/> { <br/> int i,j,*t; <br/> t=(int*)calloc(as[0][0],(bs[0][1])*(sizeof(int))); <br/> if(as[0][1]==bs[0][0]) <br/> { <br/> for(i=1;i<=as[0][2];i++) <br/> { <br/> for(j=1;j<=bs[0][2];j++) <br/> { <br/> if(as[i][1]==bs[j][0]) <br/> { <br/> *(t+(as[i][0]*bs[0][1])+bs[j][1])+=as[i][2]*bs[j][2]; <br/> } <br/> } <br/> } <br/> } <br/> else <br/> printf("\nYOUR MATRICES ARE NOT SUITABLE FOR MULTIPLECTION"); <br/> sp(t,r,as[0][0],bs[0][1]); <br/> free(t); <br/> } |
Source projectgeek.com
