performance - 稀疏矩阵乘法的特例

Question

我正在尝试想出快速算法来查找 的结果操作，其中

• L - 对称 n x n实数矩阵。
• A - 稀疏 n x m矩阵，m < n .每行只有一个非零元素，且等于1。同时保证每一列至多有两个非零元素。

我提出了一种算法，但我觉得应该有比这更快的算法。

让我们将 A 的每一列表示为具有非零元素的行号对。如果一列只有一个非零元素，它的行号会列出两次。例如。对于以下矩阵

这样的表示会是

column 0: [0, 2]; column 1: [1, 3]; column 2: [4, 4]

或者我们可以将其列为单个数组:A = [0, 2, 1, 3, 4, 4];现在，可以计算为:

for (i = 0; i < A.length; i += 2):
  if A[i] != A[i + 1]:
     # sum of two column vectors, i/2-th column of L'
     L'[i/2] = L[A[i]] + L[A[i + 1]] 
  else:
     L'[i/2] = L[A[i]]

计算我们再做一次:

for (i = 0; i < A.length; i += 2):
  if A[i] != A[i + 1]:
    # sum of two row vectors, i/2-th row of L''
    L''[i/2] = L'[A[i]] + L'[A[i + 1]]
  else:
    L''[i/2] = L'[A[i]]

这种方法的时间复杂度为 O(mn + mn)，空间复杂度(得到最终 结果)为 O(nn)。我想知道是否有可能在空间和/或性能方面将其改进到 O(mm)？

Answer 1

第二个循环最多组合了 2m 行 L'，因此如果 m 远小于 n，则将有几行 L' 永远不会被使用。

避免计算和存储这些未使用的条目的一种方法是将您的第一个循环更改为一个函数，并且仅在需要时计算 L' 的各个元素。

def L'(row,col):
  i=col*2
  if A[i] != A[i + 1]:
    # sum of two column vectors, i/2-th column of L'
    return L[row][A[i]] + L[row][A[i + 1]] 
  else:
    return L[row][A[i]]

for (i = 0; i < A.length; i += 2):
  if A[i] != A[i + 1]:
    for (k=0;k<m;k++):
      L''[i/2][k] = L'(A[i],k) + L'(A[i + 1],k)
  else:
    for (k=0;k<m;k++):
      L''[i/2][k] = L'(A[i],k)

这应该有空间和复杂度 O(m*m)