Back to: Data Structures and Algorithms Tutorials

**Sparse Matrix:**

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

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.

1^{st} method is a coordinate list and the 2^{nd} 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:

- Row number
- Column number
- Element

Let us take the same matrix which we showed above,

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

2^{nd} 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: 1^{st} column is ‘row number’, 2^{nd} column is ‘column number’ and the 3^{rd} column is ‘element’.

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

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

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

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,

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

**Compressed Sparse Rows:**

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

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. 2^{nd} array will contain the no. of non-zero elements which will present in a row (corresponding array index number) in the sparse matrix:

Here, the 0^{th} 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 1^{st} row contains only one element.

- IA [2] = ‘1’ as the 2
^{nd}row doesn’t contain any non-zero element so it will remain the same as previous one. - IA [3] = ‘3’, 3
^{rd}row contains 2 elements and the previous value is ‘1’ in the array so add these ‘1+2 = 3’. - IA [4] = ‘5’, 4
^{th}row contains 2 elements and the previous value is ‘3’ in the array so add these ‘3+2 = 5’. - IA [5] = ‘6’, 5
^{th}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. 3^{rd} array will contain the column number of non-zero elements. Below is the array which contains non-zero elements.

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 1^{st} array + 2^{nd} array + 3^{rd} 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.