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