Ques.Write a program to implement Sparse Matrix
Answer : Matrices having mostly zero values are called sparse and matrices having most of the values are non-zero, called dense.A matrix is said to be sparse matrix if most of the elements of that matrix are 0. It implies that it contains very less non-zero elements.To check whether the given matrix is the sparse matrix or not, we first count the number of zero elements present in the matrix. Then calculate the size of the matrix. For the matrix to be sparse, count of zero elements present in an array must be greater than size/2.The sparsity of a matrix can be quantified with a score, which is the number of zero values in the matrix divided by the total number of elements in the matrix.It is expensive to represent and work with sparse matrices as they are dense,and improvement in performance can be done using operations that handle the matrix sparsity.
sparsity =count zero elements / total elements
Example : A=[[1,0,0,0] ,
[0,1,0,0] ,
[0,0,2,0]]
size/2 = 16/2 = 8 and no.of zer0's = 9 so, (No.of zero's) > (size / 2 ) > 9> 8 therefore A is a sparse matrix .
Addition using sparse matrices :
X = [[0,7,0],[0 ,0,6],[0 ,8,0]]
Y = [[0,0,1],[0,0,3],[4,0,9]]
result = [[0+0, 7+0,0+1], [ 0+0,0+0,0+3],[0+4,8+0,0+9]]=[[0.7,1],[0,0,3],[4,8,9]]
Transpose of a matrix :
X = [[1,2,3],[4,5,6],[7,8,9]] =[[1,4,7],[2,5,8],[3,6,9]]
Program to find whether the given matrix is a sparse matrix or not :
|
a = [[4, 0, 0,0],[0, 5, 0,0],[0, 0, 6,0],[0,0,0,1]]
c = 0
row = len(a)
col = len(a[0])
size = row * col
for i in range(0, row):
for j in range(0, col):
if(a[i][j] == 0):
c = c+ 1
if(c > (size/2)):
print("Given matrix is a sparse matrix")
else:print("Given matrix is not a sparse matrix")
|
Output : Given matrix is a sparse matrix
Program to show addition of sparse matrix :
|
X = [[0,7,0],
[0 ,0,6],
[0 ,8,0]]
Y = [[0,0,1],
[0,0,3],
[4,0,9]]
result = [[0,0,0],
[0,0,0],
[0,0,0]]
for i in range(len(X)):
for j in range(len(X[0])):
result[i][j] = X[i][j] + Y[i][j]
for r in result:
print(r)
|
Output :
[0, 7, 1]
[0, 0, 9]
[4, 8, 9]
Program to show transposition :
|
X = [[12,7,2],
[4 ,5,1],
[3 ,8,6]]
result = [[0,0,0],
[0,0,0],[0,0,0]]
for i in range(len(X)):
for j in range(len(X[0])):
result[j][i] = X[i][j]
for r in result:
print(r)
|
Output :
[12, 4, 3]
[7, 5, 8]
[2, 1, 6]
For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments CLICK HERE
| 
| 
