如何在 Python 中不使用 numpy 将两个稀疏矩阵相乘？

Question

我是编程新手，我是第一次使用 Whosebug，大家好！所以，这就是我问这个的原因：我正在尝试将两个稀疏矩阵相乘，而没有 numpy 或其他可能对 python 库有帮助的函数。我使用列表作为存储非零元素的数据结构。每个非零元素都是一个 Class ，它具有属性行、列和值。该列表仅包含 class _MatrixElement 的那些实例。我不想以 O(n^3) 的复杂度来执行此计算，因为遍历两个矩阵的每一行并在后面进行数学运算是没有意义的，因为大多数元素都是 0。这是我到目前为止写的代码：

 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

稍后编辑：我使用本网站的算法作为指导改进了我的算法link here，在我运行我的程序之后，结果如下：

在大行中，结果是正确的。唯一的问题是我无法理解为什么程序不将 2 1 2 与 2 1 1 16 相加。结果来自以下输入：

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

第二个矩阵转置后我们将有：

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

结果应该是：

然而我的结果与我应该得到的结果不同。有人可以解释为什么不执行该总和吗？

如果有人能提供帮助，我将不胜感激！感谢您的宝贵时间！

Answer 1

scipy.sparse实现可以使用。另外，您可以使用此算法 [link]1

如何在 Python 中不使用 numpy 将两个稀疏矩阵相乘？

How can I multiply two sparse Matrix, without using numpy in Python?

python

matrix

time-complexity

sparse-matrix

multiplication