5

行列のトレースを 3 乗と 4 乗で計算する必要があり、可能な限り高速である必要があります。

ここでの行列は単純なグラフの隣接行列であるため、正方対称であり、そのエントリは常に 1 または 0 であり、対角要素は常に 0 です。

行列の 2 乗へのトレースの最適化は自明です。

  • トレースには対角線のエントリ (i,i) のみが必要で、他はすべてスキップします
  • 行列は対称であるため、これらのエントリは i 番目の行のエントリを 2 乗して合計したものにすぎません。
  • エントリは 1 または 0 であるため、二乗演算はスキップできます。

ウィキペディアで見つけた別のアイデアは、アダマール積のすべての要素、つまりエントリごとの乗算を要約することでしたが、この方法を 3 と 4 の累乗に拡張する方法がわかりません。

http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Propertiesを参照してください。

盲目なだけかもしれませんが、簡単な解決策が思いつきません。

最終的には C++ の実装が必要ですが、それは質問にとって重要ではないと思います。

助けてくれてありがとう。

4

2 に答える 2

2

トレースは固有値の合計であり、行列べき乗の固有値はそのべき乗に対する固有値です。

つまり、l_1,...,l_n が行列の固有値である場合、trace(M^p) = 1_1^p + l_2^p +...+l_n^p となります。

マトリックスによっては、固有値を計算してから合計したい場合があります。行列のランクが低い場合 (または低ランクの行列で十分に近似できる場合)、固有値を非常に安価に計算できます (部分固有値分解の複雑さは O(n*k^2) で、k はランクです)。

編集:コメントで、1600x1600 であると述べています。この場合、すべての固有値を見つけることは問題ありません。これは、このhttp://code.google.com/p/redsvd/に使用できる多くの C++ コードの 1 つです。

于 2012-02-29T07:58:53.127 に答える
1

わかりました、私はこれを自分で考え出しました。私が知らなかった重要なことはこれでした：

A が有向グラフまたは無向グラフ G の隣接行列である場合、行列 An (つまり、A の n 個のコピーの行列積) には興味深い解釈があります。無向) 頂点 i から頂点 j までの長さ n のウォーク。これは、たとえば、無向グラフ G の三角形の数が正確に A^3 を 6 で割ったトレースであることを意味します。

( http://en.wikipedia.org/wiki/Adjacency_matrix#Propertiesからコピー)

疎グラフを処理し、行列の代わりに隣接リストを使用する場合、ノード i から i までの特定の長さのパスの数を n 個のすべてのノードについて取得することは、基本的に O(n) で実行できます。

それにもかかわらず、あなたの答えに感謝します!

于 2012-03-12T14:33:23.477 に答える