In this article, we’ll take a look at a data structure that is used to implement a Sparse Matrix in Python. Let’s get started.
What is a Sparse Matrix?
A sparse matrix is a type of matrix that has many zero elements. That is, most of the items in a sparse matrix are zeroes, hence the name, and so most of the memory occupied by a sparse matrix constitutes zeroes. For example, the following matrix is a sparse matrix:
A = [
[0, 4, 0, 0],
[2, 0, 0, 5],
[0, 0, 0, 0],
[0, 0, 0, 1]
]
As you can see, except for four items, the rest are zeroes, and these redundant zeroes take up a lot of space in memory.
A sparse matrix is an optimized way of storing such matrices. It is essentially an ordered list of the items that are not zeroes. Every row in the sparse matrix stores the row and column of the non-zero element, as well as the non-zero element itself.
So, for the above matrix A, it’s sparse counterpart will look like this:
A = [
[0, 1, 4],
[1, 0, 2],
[1, 3, 5],
[3, 3, 1]
]
In the first row, the elements are 0, 1, and 4, so item 4 is at index 0, 1. Similarly, 2 is at index 1, 0; etc.
It is clear that this version takes up less space than the normal version, and in case the matrix is huge, a sparse matrix takes significantly less space.
In order to use this matrix as a sparse matrix, we need to implement it in a class, and define methods for input, printing, addition, subtraction, multiplication, etc.
Sparse Matrix in Python
Let us look at the class definition of a sparse matrix in Python.
class Sparse:
def __init__(self, rows, columns):
self._matrix = []
self._num = 0
self._rows = rows
self._columns = columns
def __repr__(self):
prnt = f"Shape: {self._rows} x {self._columns}\n"
for lst in self._matrix:
prnt += lst.__repr__() + '\n'
prnt += f"Total: {self._num}"
return prnt
def insert(self, row, column, value):
if row < 0 | column < 0 | row >= self._rows | column >= self._columns:
raise ValueError("Invalid row or column")
if(value == 0):
raise ValueError("Zeroes are not included in a sparse matrix")
filled = False
for i in range(self._num):
if(self._matrix[i][0] < row):
continue
elif(self._matrix[i][0] > row):
self._matrix.insert(i, [row, column, value])
self._num += 1
filled = True
break
elif(self._matrix[i][1] < column):
continue
elif(self._matrix[i][1] > column):
self._matrix.insert(i, [row, column, value])
self._num += 1
filled = True
break
else:
raise ValueError("The position is already filled")
if(filled == False):
self._matrix.append([row, column, value])
self._num += 1
return
def remove(self, row, column):
if row < 0 | column < 0 | row >= self._rows | column >= self._columns:
raise ValueError("Invalid row or column")
for i in range(num):
if(self._matrix[i][0] == row | self._matrix[i][1] == column):
return pop(i)
return None
def size(self):
return self._num
def shape(self):
return tuple((self._rows, self._columns))
def display(self):
print(self)
def add(self, obj):
if(isinstance(obj, Sparse) != True):
raise TypeError("add() method needs an object of type Sparse")
if(self.shape() == obj.shape()):
result = Sparse(self._rows, self._columns)
else:
raise ValueError("Invalid row or columns")
i = 0
j = 0
k = 0
while((i < self._num) & (j < obj._num)):
if(self._matrix[i][0] < obj._matrix[j][0]):
result._matrix.insert(k, self._matrix[i])
k += 1
i += 1
elif(self._matrix[i][0] > obj._matrix[j][0]):
result._matrix.insert(k, obj._matrix[j])
k += 1
j += 1
elif(self._matrix[i][1] < obj._matrix[j][1]):
result._matrix.insert(k, self._matrix[i])
k += 1
i += 1
elif(self._matrix[i][1] > obj._matrix[j][1]):
result._matrix.insert(k, obj._matrix[j])
k += 1
j += 1
else:
result._matrix.insert(k, list([self._matrix[i][0], self._matrix[i][1], self._matrix[i][2] + obj._matrix[j][2]]))
k += 1
i += 1
j += 1
while(i < self._num):
result._matrix.insert(k, self._matrix[i])
k += 1
i += 1
while(j < obj._num):
result._matrix.insert(k, obj._matrix[j])
k += 1
j += 1
result._num = k
return result
def fast_transpose(self):
occurrence = []
index = []
for i in range(self._columns):
occurrence.append(0)
for i in range(self._num):
occurrence[self._matrix[i][1]] += 1
index.append(0)
for i in range(1, self._columns):
index.append(index[i-1] + occurrence[i-1])
result = Sparse(self._columns, self._rows)
result._num = self._num
for i in range(self._num): result._matrix.append(list())
for i in range(self._num):
result._matrix[index[self._matrix[i][1]]] = list([self._matrix[i][1], self._matrix[i][0], self._matrix[i][2]])
index[self._matrix[i][1]] += 1
return result
The above definition is quite large, so we will look at each function one by one:
1. The __init__ method
For each sparse matrix, we require the number of rows and columns initially, which is passed to the constructor, which creates an empty sparse matrix.
2. The __repr__ method
This will return a string that will be printed on the string when print() is called on the object. In our case, we are printing the shape and size of the matrix, as well as the actual sparse matrix.
3. Insertion and Removal in a Sparse Matrix
To insert a non-zero item at a certain position, we simply traverse through the matrix to find the new item’s correct position and insert it there. We compare the row first, and then if we find that the rows match, we compare the column. One of these must be different, otherwise, we raise an exception.
Before doing all this, we need to validate the input, the given item mustn’t be zero and the positions must reside inside the matrix.
To remove an item at a given position, the procedure is as simple as finding the position in the matrix and popping the entire row.
4. Addition of Two Sparse Matrices
Adding two sparse matrices is very similar to merging two sorted lists.
The two matrices are basically lists that contain other lists that represent rows. And these inner lists are sorted in the sense that the first and second items of each list (row and column index of each value) are arranged in ascending order.
We create three indexes: i, j, and k.
iis the index of the next item in the first matrix.jis the index of the next item in the second matrix.kis the index of the next item in the result matrix.
We then compare the i‘th item in the first matrix and the j‘th item in the second matrix. Whichever item is supposed to come first based on its row and column index is inserted into the result matrix and we increment the respective indexes.
If both the items have the same row and column index, then certainly they need to be added together, and once we do that, their sum is inserted into the result matrix.
In the end, one of the input matrices will be completed, at this point, we simply insert all items from the other matrix to the result matrix and we will have the sum of the two matrices.
5. Fast Transpose of a Sparse Matrix
Transposing a sparse matrix is simple enough, we just have to swap the row and column values and then sort the rows in the sparse matrix. But such an operation is very ineffective, and the way a sparse matrix is constructed, we have a much faster way to transpose this matrix.
We will first create two lists that will aid in the algorithm.
The first list is called occurrence, and it will store the number of times each column index appears in the sparse matrix. So, it’s size will be the column size of the sparse matrix, and each index will represent that column. Initially, it will be filled with zeroes, and later, we will traverse through the sparse matrix and look for the column values of each item, and we will increment that index in the occurrence list.
The second list is called the index list. In this list, we will store the resulting index of each item in the original sparse matrix when it is converted to the sparse matrix. So, index[i] will have the new index of the first item with column index i in the original matrix. To do this, we first store 0 at index[0], which means that the first item with column index 0 in the original matrix will go in the 0’th index in the transpose matrix. Then to calculate index[i] we add index[i-1] and occurrence[i-1].
After this, we look at each item in the sparse matrix, we find the item’s column index, we look for the value in the index list at that index, and we use that value as the new index in the transpose matrix.
After this, we increment the index value we used so that the next item with the same column index will go to the next index in the transpose.
Doing this, we can transpose a sparse matrix very efficiently.
The Output
First, we create two sparse matrices:
Now we do addition and fast transpose operations:
Conclusion
In cases where matrices are mostly filled with zeroes, sparse matrices use much less storage and are much more efficient. We discussed what these are, how to create them and then implemented them, and finally, we confirmed that with the output that we get by running our code.