Sparse Matrices

Sparse Matrices are those which have a high ratio of number of zero elements to that of non - zero elements, that is, the matrix is sparsely populated with non- zero elements. Here's a simple program for sparse matrix addition.

                            

The matrices are given in the form of 3-tuple representation.

A 3- tuple representation means that matrices are stored in the form of a 2-dimensional  array, with three columns andthe number of rows the same as the no. of non-zero elements in the matrix. The first column describes the row index of an element, the second describes the column index and the third describes the value of the element. Usually, the first row (index 0) is used to describe the total no. of rows, columns and non-zero elements. Sparse Matrices can be provided in both row major and column major order, the program below follows row major order.

#include <stdio.h >
#include < stdlib.h >

int main()
{   int a[10][3],b[10][3],i,nz_1,nz_2,k1,k2,k3,c[20][3],m_1,n_1,m_2,n_2;       //DECLARING ALL THE VARIABLES

    printf("\tFIRST MATRIX\n");
 
    printf("enter no of rows and columns in the sparse matrix:");            //INPUT ALL DATA FOR FIRST MATRIX
    scanf("%d %d",&m_1,&n_1);
 
    a[0][0] = m_1; a[0][1] = n_1;
 
    printf("enter no of non zero numbers:");
    scanf("%d",&nz_1);
 
    a[0][2] = nz_1;
 
    printf("enter sparse matrix in 3 tuple form: ");
 
    for(i=1;i < =nz_1;i++)
    scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);
 
    printf("\tSECOND MATRIX\n");
 
    printf("enter no of rows and columns in the sparse matrix:");
    scanf("%d %d",&m_2,&n_2);
                                                                           //INPUT ALL DATA FOR SECOND MATRIX
    b[0][0] = m_2; b[0][1] = n_2;
 
    printf("enter no of non zero numbers:");
    scanf("%d",&nz_2);
     
    b[0][2] = nz_2;
    
    printf("enter sparse matrix in 3 tuple form: ");
    
    for(i=1;i < =nz_2;i++)
    scanf("%d %d %d",&b[i][0],&b[i][1],&b[i][2]);
    
    k1=1;k2=1;k3=1;
    
    printf("\tADDITION\n");                                       //MATRIX ADDITION
    
    while(k1 < =nz_1 && k2 < =nz_2)
    {   if(m_1!=m_2 || n_1!=n_2)                              //CONDITION FOR MATRIX ADDITION
        {printf("can't be added");break;}
        if(a[k1][0] < b[k2][0])
        {   c[k3][0]=a[k1][0];
            c[k3][1]=a[k1][1];                                       
            c[k3][2]=a[k1][2];
            k3++;k1++;
        }
        else if(b[k2][0] < a[k1][0])
        {   c[k3][0]=b[k2][0];
            c[k3][1]=b[k2][1];
            c[k3][2]=b[k2][2];
            k3++;k2++;
        }
       else if ( a[k1][0] == b[k2][0] )
  {
  if ( a[k1][1] < b[k2][1] )
  {
   c[k3][0] = a[k1][0];
   c[k3][1] = a[k1][1];
   c[k3][2] = a[k1][2];
   k3++;k1++;
  }
  else
  if ( a[k1][1] > b[k2][1] )
  {
   c[k3][0] = b[k2][0];
   c[k3][1] = b[k2][1];
   c[k3][2] = b[k2][2];
   k3++;k2++;
  }
  else
  {
   c[k3][0] = b[k2][0];
   c[k3][1] = b[k2][1];
   c[k3][2] = a[k1][2] + b[k2][2];
   k3++;k2++;k1++;
  }
  } // else

    }
    while ( k1 < = nz_1 )
 {
  c[k3][0] = a[k1][0];                       //IN CASE ELEMENTS ARE STILL LEFT FROM FIRST MATRIX
  c[k3][1] = a[k1][1];
  c[k3][2] = a[k1][2];
  k3++;k1++;
 } //while

 while ( k2 < = nz_2 )
 {
  c[k3][0] = b[k2][0];
  c[k3][1] = b[k2][1];                       //IN CASE ELEMENTS ARE STILL LEFT IN SECOND MATRIX
  c[k3][2] = b[k2][2];
  k3++;k2++;
 } // while
 c[0][0] = a[0][0];
 c[0][1] = a[0][1];
 c[0][2] = k3-1;

    printf("\tADDED MATRIX\n");
    for(i=0;i < k3;i++)
    printf("%d %d %d\n",c[i][0],c[i][1],c[i][2]);



    return 0;
}

Add Comment

algorithm, c, data structure, programming

Thursday, 16 October 2014

Share

Like

G+

Tweet

Tweet

Related Posts