Representation of Sparse Matrices

A matrix is a two-dimensional data object made of m rows and n columns, therefore having m ´ n values. When m=n, we call it a square matrix.
 
The most natural representation is to use two-dimensional array A[m][n] and access the element of ith row and jth column as A[i][j]. If a large number of elements of the matrix are zero elements, then it is called a sparse matrix.
 
Representing a sparse matrix by using a two-dimensional array leads to the wastage of a substantial amount of space. Therefore, an alternative representation must be used for sparse matrices. One such representation is to store only non- zero elements along with their row positions and column positions. That means representing every non-zero element by using triples (i, j, value), where i is a row position and j is a column position, and store these triples in a linear list. It is possible to arrange these triples in the increasing order of row indices, and for the same row index in the increasing order of column indices. Each triple (i,j,value) can be represented by using a node having four fields as shown in the following:

Struct snode
{
Int row,col,val;
Struct snode *next;
};

So a sparse matrix can be represented using a list of such nodes, one per non–zero element of the matrix. For example, consider the sparse matrix shown in following Figure.

This matrix can be represented using the linked list shown in following Figure.

Linked list representation of sparse matrix of above matrix

# include <stdio.h>
# include <stdlib.h>
struct snode {
	int row, col, val;
	struct snode *link;
};

struct snode *insert(struct snode *, int, int, int);
void printlist(struct snode *);
struct snode *sadd(struct snode *, struct snode *);
//struct pnode *sortlist(struct pnode *);

struct snode *insert(struct snode *p, int r, int c, int val) {
	struct snode *temp;
	if (p == NULL) {
		p = (struct snode *) malloc(sizeof(struct snode));
		if (p == NULL) {
			printf("Error\n");
			exit(0);
		}
		p->row = r;
		p->col = c;
		p->val = val;
		p->link = NULL;
	} else {
		temp = p;
		while (temp->link != NULL)
			temp = temp->link;
		temp->link = (struct snode *) malloc(sizeof(struct snode));
		if (temp->link == NULL) {
			printf("Error\n");
			exit(0);
		}
		temp = temp->link;
		temp->row = r;
		temp->col = c;
		temp->val = val;
		temp->link = NULL;
	}
	return (p);
}

/* A function to add two sparse matrices */
struct snode *sadd(struct snode *p, struct snode *q) {
	struct snode *r = NULL;
	int val;
	while ((p != NULL) && (q != NULL)) {
		if (p->row < q->row) {
			r = insert(r, p->row, p->col, p->val);
			p = p->link;
		} else if (p->row > q->row) {
			r = insert(r, q->row, q->col, q->val);
			q = q->link;
		} else if (p->col < q->col) {
			r = insert(r, p->row, p->col, p->val);
			p = p->link;
		} else if (p->col > q->col) {
			r = insert(r, q->row, q->col, q->val);
			q = q->link;
		} else {
			val = p->val + q->val;
			r = insert(r, p->row, p->col, val);
			p = p->link;
			q = q->link;
		}
	}
	while (p != NULL) {
		r = insert(r, p->row, p->col, p->val);
		p = p->link;
	}
	while (q != NULL) {
		r = insert(r, q->row, q->col, q->val);
		q = q->link;
	}
	return (r);
}

void printlist(struct snode *p) {
	printf("The resultant sparse matrix is\n");
	while (p != NULL) {
		printf("%d %d % d\n", p->row, p->col, p->val);
		p = p->link;
	}
}
int main() {
	int r, n, c, val;
	struct snode *s1 = NULL;
	struct snode *s2 = NULL;
	struct snode *result = NULL;
	printf("Enter the number of non-zero terms in the sparse matrix1 \n");
	scanf("%d", &n);
	printf("Enter the terms in the sparse matrix1 in the increasing 
order of row indices and for the same row index in the increasing order 
of row indices and for the same row index in the increasing order of 
column indices \n");
	while (n-- > 0) {
		printf("Enter the row number, column number, and value\n");
		scanf("%d %d%d", &r, &c, &val);
		s1 = insert(s1, r, c, val);
	}
	printf("Enter the number of non-zero terms in the sparse matrix1 \n");
	scanf("%d", &n);
	printf("Enter the terms in the sparse matrix2 in the increasing 
order of row indices and for the same row index in the increasing order 
of row indices and for the same row index in the increasing order of 
column indices \n");
	while (n-- > 0) {
		printf("Enter the row number, column number, and value\n");
		scanf("%d %d%d", &r, &c, &val);
		s2 = insert(s2, r, c, val);
	}
	result = sadd(s1, s2);
	printf("The result of addition is\n");
	printlist(result);
	getchar();
	return 0;
}

Explanation

1. In order to add two sparse matrices represented using the sorted linked lists as shown in the preceding program, the lists are traversed until the end of one of the lists is reached.
2. In the process of traversal, the row indices stored in the nodes of these lists are compared. If they don’t match, a new node is created and inserted into the resultant list by copying the contents of a node with a lower value of row index. The pointer in the list containing a node with a lower value of row index is advanced to make it point to the next node.
3. If the row indices match, column indices for the corresponding row positions are compared. If they don’t match, a new node is created and inserted into the resultant list by copying the contents of a node with a lower value of column index. The pointer in the list containing a node with a lower value of column index is advanced to make it point to the next node.
4. If the column indices match, a new node is created and inserted into the resultant list by copying the row and column indices from any of the nodes and the value equal to the sum of the values in the two nodes.
5. After this, the pointers in both the lists are advanced to make them point to the next nodes in the respective lists. This process is repeated in each iteration. After reaching the end of any one of the lists, the iterations come to an end and the remaining nodes in the list whose end has not been reached are copied, as it is in the resultant list.

Points to Remember

1. If the sparse matrices to be added have n and m non-zero terms, respectively, then the linked list representation of these sparse matrices contains m and n terms, respectively.
2. Since sadd traverses each of these lists sequentially, the maximum number of iterations that sadd will make will not be more than m+n. So the computation time of sadd is O(m+n).