I am new into programming and I am using for the first time stackoverflow so Hi to everyone! So, this is the reason why am I asking this: I am trying to multiply two sparse Matrix without numpy or other functions that might help me from python libraries. I am using a list as the Data Structure for storing the non zero elements. Each non zero elements is a Class which has as attributes row, col and the value. The list contains only those instances of the class _MatrixElement. I want to perform this computation not in a complexity of O(n^3), as it makes no sense to go through each line of both matrix and do the math behind because most of the elements are 0. This is the piece of code I wrote so far:
class _MatrixElement:
def __init__(self, row ,col, value):
self.row = row
self.col = col
self.value = value
class SparseMatrix:
def __init__(self, numRows, numCols):
self._numRows = numRows
self._numCols = numCols
self._elementList = list()
def numRows(self):
return self._numRows
def numCols(self):
return self._numCols
def __setitem__(self, ndxTuple, scalar):
ndx = self._findPosition(ndxTuple[0], ndxTuple[1])
if ndx is not None:
if scalar != 0.0:
self._elementList[ndx].value = scalar
else:
self._elementList.pop(ndx)
else:
if scalar != 0.0:
element = _MatrixElement(ndxTuple[0], ndxTuple[1], scalar)
self._elementList.append(element)
def __getitem__(self, row, col):
assert row >= 0 and row < self.numRows(), "Subscript out of range"
assert col >= 0 and col < self.numCols(), "Subscript out of range"
ndx = self._findPosition(row, col)
if ndx is not None:
return self._elementList[ndx]
else:
raise Exception("The element is not in the matrix")
def _findPosition(self, row, col):
"""Find the position of the non zero element in the list, using the row and col as parameters"""
n = len(self._elementList)
for i in range(n):
if (row == self._elementList[i].row and
col == self._elementList[i].col):
return i
return None
def transpose(self):
newTransposeMatrix = SparseMatrix(numRows=self.numCols(), numCols=self.numRows())
for elem in self._elementList:
tmp_row = elem.row
elem.row = elem.col
elem.col = tmp_row
newTransposeMatrix._elementList.append(elem)
return newTransposeMatrix
def __mul__(self, otherMatrix):
assert isinstance(otherMatrix, SparseMatrix), "Wrong matrix type"
assert self.numCols() == otherMatrix.numRows(), "The two matrices can't be multiplied"
transpMatrix = otherMatrix.transpose()
sparseNewMatrix = SparseMatrix(numRows=self.numRows(), numCols=otherMatrix.numRows())
for apos in range(len(self._elementList)):
r = self._elementList[apos].row
for bpos in range(len(transpMatrix._elementList)):
c = transpMatrix._elementList[bpos].row
tmpa = apos
tmpb = bpos
the_sum = 0
while (tmpa < len(self._elementList) and (tmpb < len(transpMatrix._elementList)) and (self._elementList[tmpa].row == r
and transpMatrix._elementList[tmpb].row == c)):
if self._elementList[tmpa].col > transpMatrix._elementList[tmpb].col:
tmpa += 1
elif self._elementList[tmpa].col < transpMatrix._elementList[tmpb].col:
tmpb += 1
else:
the_sum += self._elementList[tmpa].value * transpMatrix._elementList[tmpb].value
tmpa += 1
tmpb += 1
if the_sum != 0:
sparseNewMatrix.add(_MatrixElement(r, c, the_sum))
return sparseNewMatrix
Later EDIT: I have improved my algorithm using as guide the algorithm from this websitelink here and after I run my program, the result is the following one:
1 2 10
1 1 96
2 1 2
2 2 5
2 1 16
In big lines, the result is correct. The only problem is that I cannot understand why the program does not sum 2 1 2 with 2 1 1 16. The result comes from the following input:
Row Col Val Row Col Val
1 2 10 1 1 2
1 3 12 1 2 5
2 1 1 2 2 1
2 3 2 3 1 8
After second matrix is transposed we'll have:
Row Col Val Row Col Val
1 2 10 1 1 2
1 3 12 1 3 8
2 1 1 2 1 5
2 3 2 2 2 1
The result should be:
1 1 96
1 2 10
2 1 18
2 2 5
However my result is different from the one I should get. Can somebody explain why that sum is not performed?
If somebody can help, I would be very grateful! Thank you for your time!