Sparse Matrix

Sparse Matrix:

A sparse matrix is a matrix in which there is more number of zero elements.

Sparse Matrix

Here, we have an example matrix of order 7 by 5 and you can see that it is having very few non-zero elements i.e. 4, 3, 7, 2, 9, 8. There are only 8 non-zero elements and the rest are zeroes. Mostly in the statistical data or survey data, Data may be presented in the form of a matrix and there may be a lot of zero values. If so then if you are using sparse matrices in a program then we may be having a lot of zero values. For which we may be wasting space and also processing time.

So, we want to store a matrix in less amount of space and the processing is also less. So, what we should do? We should store only non-zero elements. For storing non-zero elements, there is more than one approach available.

Sparse Matrix

1st method is a coordinate list and the 2nd is a compressed sparse row. The coordinate list method is also called a 3-column representation. So first we will see the coordinate list or 3 column representation method.

Coordinate List / 3-Col representation:

In this method, for every non-zero element, we need three things:

  1. Row number
  2. Column number
  3. Element

Let us take the same matrix which we showed above,

Coordinate List / 3-Col representation

1st element is present on row no. ‘1’, column no. ‘5’ and element is ‘4’.

2nd element is present on row no. ‘1’, column no. ‘5’ and element is ‘4’.

So, we will have a couple of three values that is column number, row number, and the element. So, we can have the list of couples so we can call them coordinates or we can represent them in the form of columns. So that is 3 columns: 1st column is ‘row number’, 2nd column is ‘column number’ and the 3rd column is ‘element’.

Coordinate List / 3-Col representation

Now let us represent those non-zero values in these three columns. Element ‘4’ will be filled as:

Coordinate List / 3-Col representation

Here we have left the 1st-row blank. We will fill this in the end. Now ‘3’ will be filled as:

Coordinate List / 3-Col representation

Now in this way, we will fill all the elements as:

Coordinate List / 3-Col representation

Now we will fill the first row as we left it empty. We will use the first row to store the information about the sparse matrix means its dimensions and the total number of non-zero elements. So,

Coordinate List / 3-Col representation

Now let us look at the second method which is compressed sparse rows.

Compressed Sparse Rows:

Compressed Sparse Rows

In this method, a sparse matrix is represented using 3 arrays. 1st array is a set of non-zero elements:

Sparse Matrix in C

We have taken all these non-zero elements in the same order in which they are appearing. Don’t change the order. We need an array for rows. 2nd array will contain the no. of non-zero elements which will present in a row (corresponding array index number) in the sparse matrix:

Sparse Matrix in C

Here, the 0th element of this array will be 0 as indices start in the array from 0, and in matrices, it starts from 1. Next, IA [1] = ‘1’ as 1st row contains only one element.

  • IA [2] = ‘1’ as the 2nd row doesn’t contain any non-zero element so it will remain the same as previous one.
  • IA [3] = ‘3’, 3rd row contains 2 elements and the previous value is ‘1’ in the array so add these ‘1+2 = 3’.
  • IA [4] = ‘5’, 4th row contains 2 elements and the previous value is ‘3’ in the array so add these ‘3+2 = 5’.
  • IA [5] = ‘6’, 5th row contains only one element so add ‘1’ to previous value as ‘5 + 1 = 6’.

These values are not showing the number of non-zero elements in a particular row. Suppose we want to know no. of elements in row 5 then,

= A [5] – A [4] = 6 – 5 = 1 element.

For row 3,

= A [3] – A [2] = 3 – 1 = 2 elements.

In this way, we will fill this array. 3rd array will contain the column number of non-zero elements. Below is the array which contains non-zero elements.

Sparse Matrix in C

Now in the same order, we will column the number of corresponding elements in an array:


So as many elements are there that many columns will be there. So, this is another method that is called compressed sparse rows. Let us analyze a little bit upon space.

The dimension of the above matrix is 5×7, which means 35 elements including zero and non-zero elements. And if each element is an integer and is taking 2 bytes so this will be 35 * 2 = 70 bytes. And in a compressed sparse row, how much space is required?

Size of 1st array + 2nd array + 3rd array,

= (6 + 6 + 6) * 2 = 36 bytes. It requires only 36 bytes.

In the next article, I am going to discuss the Addition of Sparse Matrices with Examples. Here, in this article, I try to give a brief Introduction to Sparse Matrices and I hope you enjoy this Sparse Matrices article.

Leave a Reply

Your email address will not be published.