2

我正在尝试提出快速算法来查找洛杉矶操作结果，其中

  • 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];现在，L' = 洛杉矶可以计算为：

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]]

为了计算L''=AtL'，我们再做一次：

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(m n + m n)，空间复杂度（得到最终洛杉矶结果）是 O(n n)。我想知道是否有可能在空间和/或性能方面将其提高到 O(m m)？

4

3 回答 3

0

第二个循环最多组合 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)

于 2012-04-15T18:10:35.160 回答
0

操作Transpose(A) * L如下：

对于 A 的每一列，我们看到：

column 1 has `1` in row 1 and 3
column 2 has `1` in row 2 and 4
column 3 has `1` in row 5

输出矩阵B = Transpose(A) * L有三行，它们等于：

Row(B, 1) = Row(A, 1) + Row(A, 3)
Row(B, 2) = Row(A, 2) + Row(A, 4)
Row(B, 3) = Row(A, 5)

如果我们相乘C = B * A：

Column(C, 1) = Column(B, 1) + Column(B, 3)
Column(C, 2) = Column(B, 2) + Column(B, 4)
Column(C, 3) = Column(B, 5)

如果您以算法方式完成此操作，您应该会实现与 Peter de Rivaz 所建议的非常相似的东西。

于 2012-04-15T18:30:31.643 回答
0

您的算法的时间复杂度是 O(n^2)，而不是 O(m*n)。L 的行和列的长度为 n，A 数组的长度为 2n。

如果 a[k] 是 A 的第 k 行有 1 的列，那么你可以写：

A[k,i] = δ(a[k],i)

乘积 P = A^T*L*A 为：

P[i,j] = Σ(k,l) A^T[i,k]*L[k,l]*A[l,j]
       = Σ(k,l) A[k,i]*L[k,l]*A[l,j]
       = Σ(k,l) δ(a[k],i)*L[k,l]*δ(a[l],j)

如果我们反过来看看L的元素发生了什么，我们看到L[k,l]被添加到P[a[k],a[l]]中，很容易得到O(m^ 2) 空间复杂度使用 O(n^2) 时间复杂度。

因为 a[k] 是为所有 k=0..n-1 定义的，所以我们知道 L 的每个元素都必须出现在乘积中的某个位置。因为 L 中有 O(n^2) 个不同的元素，所以你不能做得比 O(n^2) 时间复杂度更好。

于 2012-04-15T20:44:13.963 回答