CHOLMOD から clique 情報を取り出せるようになった

ついに CHOLMOD から clique 情報を計算する方法が分かった。

そのまえに、Matlab のいくつかのテクニックについて。
etreeplot で elimination tree の表示ができるが、このままだとノード番号が表示されず、若干使いづらい。
これは treelayout で情報を得ると表示できる。

p = amd(A);
[parent,post] = etree(A(p,p));
figure(1);
etreeplot(A(p(post),p(post)));
hold on;

[x,y] = treelayout(parent,post);
for i=1:n
    text(x(post(i)),y(post(i)),sprintf('%d',i));
end
hold off;
とすれば、elimination tree のノード番号を表示できる。


また、Matlab では、system 関数でコマンドを実行できるが、この2つめで出力を取り込むことができる。
たとえば、a.txt の内容を取り込むのであれば、fopen などをしなくても
[status,result] = system('cat a.txt');
とすればOKである。
a.txt に
A = [1,2; 3,4];
と書いておいてから

[status,result] = system('cat a.txt');

eval(result);

とすると、もちろん、 A に行列が格納される。

このあたりは、他の C 言語のプログラムや awk などで処理した結果を取り込むのに便利である。

今日の本題の clique 情報だが、基本的に supernode ひとつにつき clique をひとつ生成すればよく、この場合は supernode に含まれる頂点と、それらに隣接する頂点で clique を構成することができる。

ただし、maximal clique をまじめに取った場合に比較して、より fill-in が多くなってしまう。

このあたりは BLAS で高速化されるはずだが、どの程度の高速化になるかはやってみないと分からないかもしれない。

今日の作業内容： CHOLMOD 確認 3h

今日のランチ：たちばな カツオ丼

明日の予測作業時間：4h