performance - スパース行列乗算の特殊なケース

Question

操作の結果を見つけるための高速アルゴリズムを考え出そうとしています。

• L-はn x n実数の対称行列です。
• A-はスパースn x m行列ですm < n。各行にはゼロ以外の要素が1つだけあり、1に等しくなります。また、すべての列にゼロ以外の要素が最大2つあることが保証されます。

一つのアルゴリズムを思いついたのですが、これよりも速いものがあるはずだと思います。

Aのすべての列を、ゼロ以外の要素を持つ行番号のペアとして表します。列にゼロ以外の要素が1つしかない場合、その行番号は2回リストされます。たとえば、次のマトリックスの場合

そのような表現は

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（m n + m n）であり、（最終結果を得るための）空間計算量はO（n n）です。スペースやパフォーマンスの面でO（m m）に改善できるかどうか疑問に思っていますか？

Answer 1

2番目のループは最大で2m行のL'を結合するため、mがnよりもはるかに小さい場合、使用されないL'の行がいくつかあります。

これらの未使用のエントリの計算と保存を回避する1つの方法は、最初のループを関数に変更し、必要に応じて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）

Answer 2

操作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には、次と等しい 3 つの行があります。

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 が提案したものと非常によく似た結果が得られるはずです。

Answer 3

アルゴリズムの時間計算量は、O(m*n) ではなく O(n^2) です。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) 時間の複雑さよりも優れた処理を行うことはできません。