Sparse Matrices (Array Representation)

SPARSE MATRICES

Sparse matrix is a matrix that has large number of elements with a zero value. In order to efficiently utilize the memory, specialized algorithms and data structures that take advantage of the sparse structure of the matrix should be used. If we apply operations using standard matrix structures and algorithms to sparse matrices, then execution will slow down and the matrix will consume large amounts of memory. Sparse data can be easily compressed which in turn can significantly reduce memory usage.

There are two types of sparse matrices. In the first type of sparse matrix, all elements above the main diagonal have a zero value. This type of sparse matrix is also called a lower triangular matrix because if you see it pictorially, all the elements with a non-zero value appear below the diagonal. In a lower triangular matrix, A_i,j = 0 where i < j. An n x n lower triangular matrix A has one non zero element in the first row, two non-zero elements, in the second row and likewise, n non-zero elements in the n row. Figure 5.33 shows a lower triangular matrix.

To store the lower triangular matrix efficiently in memory, we can use a one-dimensional array which stores only the non-zero elements. The mapping between a two- dimensional-matrix and a one-dimensional array can be done in any one of the following ways:

(a) Row-wise mapping-here the contents of array A [] will be {1, 5, 3, 2, 7, -1, 3, 1, 4, 2, -9, 2, -8, 1, 7}

(b) Column-wise mapping-here the contents of array A[] will be {1, 5, 2, 3, -9, 3, 7, 1, 2, -1, 4, -8, 2, 1, 7}

Like a lower triangular matrix, we also have an upper triangular matrix in which Ai,j = 0 where i>j. An n × n upper triangular matrix A has n non-zero elements in the first row, n-1 non-zero elements in the second row and likewise, 1 non-zero element in the nth row. Figure 5.34 shows an upper triangular matrix.

In the second variant of a sparse matrix, elements with a non-zero value can appear only on the diagonal only on or immediately above or below the diagonal. This type of matrix is also called a tridiagonal matrix. Hence in a tridiagonal matrix, A_i,j = 0 where |i - j|>1.

In a tridiagonal matrix, if elements are present on

(a) the main diagonal, it contains non-zero elements for i-j. In all, there will be n elements.

(b) below the main diagonal, it contains non-zero elements for i=j+1. In all, there will be n-1 elements.

(c) above the main diagonal, it contains non-zero elements for i-j-1. In all, there will be n-1 elements. Figure 5.35 shows a tridiagonal matrix.

To store the tridiagonal matrix efficiently in memory, we can use a one-dimensional array which stores only the non-zero elements. The mapping between a two- dimensional matrix and a one-dimensional array can be done in any one of the following ways:

(a) Row wise mapping-here the contents of array A [] at will be {4, 1, 5, 1, 2, 9, 3, 1, 4, 2, 2, 5, 1, 9, 8, 7}

 (b) Column wise mapping-here the contents of array A[] will be {4, 5, 1, 1, 9, 2, 3, 4, 1, 2, 5, 2, 1, 8, 9, 7}

(c) Diagonal wise mapping-here the contents of array A[] will be {5, 9, 4, 5, 8, 4, 1, 3, 2, 1, 7, 1, 2, 1, 2, 9}

Array Representation of Sparse Matrices

Let us see how we can represent a sparse matrix. Consider the sparse matrix given below.

Out of 9 elements, the matrix has only two non-zero elements. This sparse matrix can be represented using the matrix given below.

• The first row gives the number of rows (3), number of columns (3), and number of non-zero elements (2) in the sparse matrix.

• The second row specifies the location and value of first non-zero element. The first non-zero value 2 is at (0, 1) location.

• Similarly, third row specifies the location and value of the next non-zero element, i.e. value 4 at (1, 2) location.

This means that in the array representation of the sparse matrix, number of rows will be one more than the number of non-zero values.

#include <stdio.h>

#include <conio.h>

void sparse_mat (int mat [3] [3], int, int, int);

void main()

{

int i, j, rows, cols, num_values = 0;

int mat [3] [3];

clrscr();

printf("\n Enter the number of rows : ");

scanf("%d", &rows);

printf("\n Enter the number of columns: ");

scanf("%d", &cols);

printf("\n Enter the elements of array: ");

for (i=0;i<rows; i++)

{

for(j=0;j<cols; j++)

{

scanf("%d", &mat [i] [j]);

}

}

printf("\n The sparse matrix is: \n");

for (i=0;i<rows; i++)

{

printf("\n");

for (j=0;j<cols;j++)

printf("%d", mat [i][j]);

}

for (i=0;i<rows; i++)

{

for (j=0;j<cols;j++)

{

if (mat [i] [j] !=0)

num_values++;

}

}

}

sparse_mat (mat, num_values, rows, cols);

getch();

}

void sparse_mat (int mat [3] [3], int num_values, int rows, int cols)

{

int new_mat [5] [3], i, j, temp_index =1;

new mat [0] [0] = rows;

new_mat [0] [1] = cols;

new_mat [0] [2] = num_values;

for (i=1;i<= rows; i++)

{

for(j=1;j<=cols;j++)

{

if (mat [i-1] [j-1] != 0):

{

new_mat [temp_index] [0] = i-1;

new_mat [temp_index] [1] = j-1;

new_mat [temp_index] [2] = mat [i-1] [j-1];

temp_index++;

}

}

}

printf("\n\n The new matrix is: \n");

for (i=0;i<=num_values; i++)

{ printf("\n");

for(j=0;j<3;j++)

printf("%d", new_mat [i][j]);

}

}

Output

Enter the number of rows : 2

Enter the number of columns 2

Enter the elements of array: 1 0 0 0

The sparse matrix is :

1 0

0 0

The new matrix is :

2 2 1

0 0 1

Note

For better performance, memory for the new matrix must be allocated using dynamic memory allocation which will be discussed later in this book. We may also represent the sparse matrix using a linked list.