How to: Implement Sparse Matrix Data Structure in C++ Using Array

3 comments - This post in romanian

The sparse matrix represents a special type of two-dimensional array consisting of a large number of elements from out of which a very high proportion is occupied by null elements. Thus, the classical declaration of a two-dimensional array in the C++ programming language leads to unnecessary use of memory by storing null values and of the processing capacity.

The declaration of sparse matrix type data structure is based on the following elements:

  • Not null values;
  • The position of the not null values in the two-dimensional array.

The advantages of using the sparse matrixes are:

  • Diminishing the memory usage requests;
  • Diminishing the processing time by eliminating the useless operations with null values.

The disadvantages of using the sparse matrixes are:

  • The memory space needed to store the sparse matrix is much larger than in the case the number of not null values is not much smaller than the number of null values;
  • More difficult implementation of the operations at matrix level due to the indirect access way through the data structure defined for storing the sparse matrix.

Storage structures for sparse matrixes:

  • Three arrays for storing the values of the line index, column index and not null value; in linear shape, the first two arrays are replaced with the linear index;
  • The article type structure with the following fields: line index, column index and the not null value; the articles are stored in an array or a linear list;
  • Array on bits for marking the position of the not null element in the linear matrix and an array to store not null values.

The two-dimensional arrays with a large number of null values are stored in the form of sparse matrixes if the null values occupy between 0.15% and 3% of the total number of elements of the matrix.
In the example below, the storage variant of the sparse matrix is the article type structure for retaining the line index, column index and not null value.

struct ElementMR{
	unsigned int i,j;
	double val;
};

The articles are stored in an array allocated in the heap memory. The number of elements in the array is given by the number of not null elements of the two-dimensional array.
In the next program, a matrix is defined in the classical way without being allocated in the heap memory. Is checked the condition of existence of the sparse matrix. If this condition is met, the two-dimensional array is converted in the sparse matrix structure type, stored as an array of articles, shown above. Conversion is done via the function ConversieToMatriceRara(double [][100],unsigned int,unsigned int,char*,unsigned int*).

#include <iostream>
 
using namespace std;
 
struct ElementMR{
	unsigned int l,c;
	double val;
};
 
ElementMR* ConversieToMatriceRara(double A[][100], unsigned int m, unsigned int n, \
char *err, unsigned int *nrEl){
	*nrEl=0;
	unsigned int i,j;
	ElementMR *pTuplu;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			if(A[i][j])
				(*nrEl)++;
	double pondere=*nrEl;
	pondere=pondere/(m*n);
	if(pondere>=0.0015 && pondere<=0.03){
		*err=1;
		pTuplu=new ElementMR[*nrEl];
		unsigned int k=0;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(A[i][j]){
					pTuplu[k].l=i+1;
					pTuplu[k].c=j+1;
					pTuplu[k].val=A[i][j];
					k++;
				}
		return pTuplu;
	}
	else{
		*err=0;
		return 0;
	}
}
 
void main(){
	double Mat[25][100],val;
	unsigned int m, n, i, j;
	unsigned int nrEl;
	char err;
	m=25;
	n=100;
	ElementMR *pMatRara=NULL;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			Mat[i][j]=0;
 
	char opt='y';
	while(opt=='y'){
		do{
			cout<<"Give the row index of the not null element: ";
			cin>>i;
		}
		while(i>25 || i==0);
		do{
			cout<<"Give the column index of the not null \
element: ";
			cin>>j;
		}
		while(j>100 || j==0);
		cout<<"Give the value of the not null element: ";
		cin>>val;
		if(!Mat[i-1][j-1])
			Mat[i-1][j-1]=val;
		else{
			cout<<"Given position contains an element with not \
null value! Overwrite the element?(y/n): ";
			cin>>opt;
			if(opt=='y')
				Mat[i-1][j-1]=val;
 
		}
		cout<<"Continue?(y/n): ";
		cin>>opt;
	}
 
	pMatRara=ConversieToMatriceRara(Mat,m,n,&err,&nrEl);
 
	if(err){
		cout<<"Structure of the type Sparse Matrix is:"<<endl;
		for(i=0;i<nrEl;i++)
			cout<<pMatRara[i].l<<"\t"<<pMatRara[i].c<<"\t"<< \
pMatRara[i].val<<endl;
		delete [] pMatRara;
	}
	else
		cout<<"Two-dimensional array does not meet the \
criteria of sparse matrix!"<<endl;
}

Significance of variables defined in main() function are:

  • Mat: two-dimensional array stored in classic format;
  • m: number of lines of the Mat array;
  • n: number of columns of the Mat array;
  • i: line index of the Mat array;
  • j: column index of the Mat array;
  • nrEl: number of not null elements of the Mat array; the number of elements of the pMatRara array allocated in the heap memory;
  • pMatRara: the address of the memory area of length nrEl where are stored the elements of the sparse matrix structure;
  • err: error indicator for the performance of the conversion from the Mat array to the structure managed by pMatRara.

The above application effectuates the initiation of the whole Mat array with null values, the validation of data entered from the keyboard, the modification of the null values with not null values for the positions specified by the keyboard, the conversion of the Mat array into the sparse matrix structure by applying the condition of the upper and lower limits of the not null elements’ weight.

, , , , ,


  1. #1 by preeti on June 17th, 2012

    thanxxxx

  2. #2 by preeti on June 17th, 2012

    thanxxxx 4 dis info…..

(will not be published)