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);
}
