In many applications, you have huge matrices, but most of the elements of the ma

Question

In many applications, you have huge matrices, but most of the elements of the matrix are zeros. It’s inefficient to store all those zeros, it’s only necessary to store the nonzero elements. Here is one approach to this idea. Define a subclass of Matrix called SparseMatrix. In a sparse matrix, we keep track of the nonzero elements in a dictionary. The keys are tuples (i,j) giving the location of the element and the value assigned to this key gives the value of the nonzero element. If a tuple (i,j) does not appear in the dictionary, the matrix element at that location is assumed to be zero. When creating or modifying a sparse matrix, we don’t want to store zero entries. In the class SparseMatrix override some (but as few as possible) of the parent class Matrix to make sparse matrices work anywhere you can put a Matrix.

Explanation / Answer

Matrix defines a real, 2-d matrix

class Matrix(object):
I am a matrix of real numbers
def __init__(self,h,w):
self._nrows = h
self._ncols = w
self._data = [0] * (self._nrows * self._ncols)

def __str__(self):
return "Matrix: " + str(self._nrows) + " by " + str(self._ncols)

def setnrows(self, w):
self._nrows = w
self.reinit()

def getnrows(self):
return self._nrows

def getncols(self):
return self._ncols

def reinit(self):
self._data = [0] * (self._nrows * self._ncols)

def setncols(self, h):
self._ncols = h
self.reinit()

def setValue(self,i,j, value):
if i < self._nrows and j < self._ncols:
self._data[i * self._nrows + j] = value
else:
raise Exception("Out of range")

def multiply(self, otherMatrix):
result = Matrix(self._nrows, otherMatrix.getncols())
# Do multiplication...
return result

def inv(self):
if self._ncols != self._nrows: raise Exception("Only square matrices are invertible")
invertedMatrix = Matrix(self._ncols, self._nrows)
invertedMatrix.setncols(self._ncols)
invertedMatrix.setnrows(self._ncols)
# INVERT!
return invertedMatrix

SparseMatix

class SparseMatrix(Matrix)
I am a matrix of real numbers

def __str__(self):
return "SparseMatrix: " + str(self._nrows) + " by " + str(self._ncols)

def reinit(self):
self._data = {}

def setValue(self,i,j, value):
self._data[(i,j)] = value:
def multiply(self, otherMatrix)
result = SparseMatrix(self._nrows, otherMatrix.getncols())
# Do multiplication...
return result

def inv(self):
if self._nrows != self._rcols: raise Exception("Only square matrices are invertible")
invertedMatrix = SparseMatrix(self._ncols, self._nrows)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.