0

与えられた:

  • ベクトル v1, v2 (nx1) ここで、各ベクトルのエントリは区間 [0,1] にあります。v1 と v2 は疎または密にすることができます

  • 密な対称行列 M (nxn) (実際には、エントリが 0 または 1 である論理行列)

  • 密行列 E (nxn) E(i,j) = 1-E(j,i) ここで、E(i,j) は区間 ]0,1[ にあります。E(i,j) = 1-E(j,i) であるこのタイプの行列の名前はありますか?

s = Sum[(v1 * v2^T) .* M] を計算したいと思います。ここで、.* は要素単位の乗算演算で、Sum は結果の行列のすべてのエントリの合計です。^T は転置操作です。

与えられた s を取得したい x = Sum[(v1 * v2^T) .* E] / s

これらの乗算を実行して x を取得する計算効率の高い方法はありますか?

ありがとう。

4

1 に答える 1

0

乗算.* Mは単なる選択であるため、選択した要素を次のように合計する方が簡単です（疑似コードでは、言語を指定しないため）：

sum = 0;
for i=1 to n
    for j = i to n
        if M(i,j) then
           sum += v1(i)*v2(j)+v1(j)*v2(i);
        endif
    endfor
 endfor

2*n^2 回の乗算と n^2 回の加算をすべて実行する代わりに、2*k 回の加算と k 回の乗算のみを実行します (ここで、k は M のゼロ以外のエントリの数であり、最大でも n^2 です)。

2 番目の操作では、それらを高速化する方法が見当たらないため、明示的に計算する必要があります。

于 2013-01-29T17:12:21.170 に答える