Let’s learn sparse matrix and its representations in java.
What is sparse matrix and its representation?
Sparse matrix is a two dimensional array also known as a sparse array. In this matrix majority of elements are zero and very few are non zero elements.
For example, consider two rows and three columns matrix. In this matrix there are only two values and the remaining are blank. This vacant place are filled with zero.
Why we are using sparse matrix?
Sparse matrix reduces the scanning time and how exactly it reduces the scanning time is, if there is m x n matrix where m = 50 and n is also = 50.
This means, for searching all the elements we require 2500 times scanning to find the value.
So instead of scanning 2500 times you can use a sparse matrix. In sparse matrix you can directly get the values that exists in the matrix.
What are the different ways of representing sparse matrix in memory?
Sparse matrix and its representations in java
There are two ways to represent sparse matrix,
- Array representation or three column form
- linked list representation
Three column form or array representation
In three column form representation there are three columns row, column and value. For example, this is 4 X 4 matrix and values are as shown below,
We have to create a sparse matrix of the above 4 X 4 matrix. For that we have three columns row, column and value.
In the above table first row is represented by total number of row, total number of column and total number of non-zero values existing in the above 4 X 4 matrix.
First total number of rows in the above 4 X 4 matrix is 4. Total number of column is 4 and total number of non-zero values is 6.
Before going to next row here is how the indexing is done in matrix,
As you can see above image, representation is in this format. For three column form representation we have to consider non-zero values.
In the next row of three column form representation, consider row 0 (of 4 X 4 matrix) at column 1 value is 3.
In next row (of 4 X 4 matrix) we have row 1 column 0 and value is 2. Next in the same row we have indexing value of column is 2 and value is 4.
Moving to the next row, R2 value exists at first and third column. So the value is 1 and 2.
In the last row (of 4 X 4 matrix) that is R3, column 1 value is 3. Here’s the complete three column form representation table,
Through this three column form representation we can directly access only non-zero values and we ignore the zero values.
Linked list representation
Now we are going to learn linked list to represent sparse matrix in java. To represent linked list we require three nodes and three nodes has a different structure. Here’s the structure,
As you can see in the above image, first node has four columns. Where first column is total row, second is total column, third is total non-zero values in that matrix and last is a pointer that point to the next row.
Similar to previous three column form representation (we had row, column, value) after three columns, one pointer is required that point next row.
Next is row node. In row node first is row number, second is pointer for next row (because any matrix after scanning all the columns you have to move to next row.
So there is one pointer that will take you to the next row) and third is pointer for column.
Last is column node. In column node first is column number, second is the value that exists in column and third is pointer for next value in the same row. Let’s understand linked list representation with an example,
I am using the same 4 X 4 matrix used in three column form representation. So for linked list representation of 4 X 4 matrix first is head node.
This head node contains four row, four column and six non-zero values. Next is pointer that will point first row of the matrix.
First row means R0 ( refer image “Indexing” above ) and its next pointer point to next row R1. Next pointer point to row 2 (R2) and its next pointer point to last row R3.
So, in row 0 first column value is 3. Since there is no another value in the same row last pointer will be null ( see image above represented as X ).
Moving to next row, that is, row one (R1) pointer points to column 0 and value is 2.
Then again it points to next column where column value is 4 and there is no other value in the same row so it is null.
Now second row ( R2 ) has two values so I have two nodes. The first in row 2 column 1, value is 1 and it points to next column value.
Column number 3 has value 2 and it does not point to next row so it is null. Coming to last row R3; column node in column 1 we have value 3 and it does not point to any other non-zero value in the same row, so it is null.
So this is all about sparse matrix and its representations in java.