最適化問題に対する超高速&安定計算

大規模最適化問題、グラフ探索、機械学習やデジタルツインなどの研究のお話が中心

行列の conversion その2

2008年10月20日 02時51分29秒 | Weblog
先日の conversion の続き。今度は以下のような別のグラフを考える。よって無向枝は (1,2), (1,6), (2,6), (3,4), (3,5), (3.6), (4,5) の7本になる。

octave:13> A
A =

100 1 0 0 0 1
1 100 0 0 0 1
0 0 100 1 1 1
0 0 1 100 1 0
0 0 1 1 100 0
1 1 1 0 0 100

octave:14> B = transpose(chol(A));
octave:15> B
B =

10.00000 0.00000 0.00000 0.00000 0.00000 0.00000
0.10000 9.99950 0.00000 0.00000 0.00000 0.00000
0.00000 0.00000 10.00000 0.00000 0.00000 0.00000
0.00000 0.00000 0.10000 9.99950 0.00000 0.00000
0.00000 0.00000 0.10000 0.09900 9.99901 0.00000
0.10000 0.09900 0.10000 -0.00100 -0.00099 9.99851

max. clique は (1,2,6) と (3,4,5,6) なので、元のグラフに対して fill-in が発生している((6,4) と (6.5))。
今度は fill-in が起こらないように、点を 1,2,6,3,4,5 の順番で並べる。

octave:31> C
C =

100 1 1 0 0 0
1 100 1 0 0 0
1 1 100 1 0 0
0 0 1 100 1 1
0 0 0 1 100 1
0 0 0 1 1 100

octave:32> D = transpose(chol(C));
octave:33> D
D =

10.00000 0.00000 0.00000 0.00000 0.00000 0.00000
0.10000 9.99950 0.00000 0.00000 0.00000 0.00000
0.10000 0.09900 9.99901 0.00000 0.00000 0.00000
0.00000 0.00000 0.10001 9.99950 0.00000 0.00000
0.00000 0.00000 0.00000 0.10001 9.99950 0.00000
0.00000 0.00000 0.00000 0.10001 0.09900 9.99901

今度は max. clique は (1,2,6), (3,6), (3,4,5) なので fill-in が発生しなかった。
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする