行列の conversion その２

先日の conversion の続き。今度は以下のような別のグラフを考える。よって無向枝は (1,2), (1,6), (2,6), (3,4), (3,5), (3.6), (4,5) の７本になる。

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 が発生しなかった。