論文読み込みの続き

今日は予定よりも時間が取れなかったが昨日の論文の続きを読んだ。
基本的な定式化については、この論文に書いてあったので、それについて理解できたのはよかった。
ただし、この論文のアルゴリズムはあまりよくないものだったようで、それ以降利用されておらず、確かに証明などは込み入っているように見える。
そこで、この論文については証明などは省くことにして、定式化が理解できたことでよいことにし、前の論文に戻ることにする。（そちらの手法の方が SDP に拡張できそうであるし）

今日の作業内容：論文読み 1h
今日のランチ：信華園 レバー野菜炒め
明日の予測作業時間：4h

先祖がえり

この前から読み始めている論文について、途中でよく分からなかったところがあるので、そのもとになっている論文を読んでいるが、そこにも解らないところがある。
その結果、

[最初に読んでいた論文]=>[もとになった論文]=>[そのもとになった論文]=>[さらにもとになった論文]

というところまで先祖がえりをしている。
一つ一つを確認しながら読み進めているので時間はかかっているが、内容としてはこれから使い物になりそうな手ごたえがある感じだ。

今日の作業内容：論文読み込み 5h
今日のランチ：味庵 鶏の唐辛子炒め
明日の予測作業時間： 5h

mex での高速化の続き

昨日に続いて、SNL 計算の Matlabプログラムを一部 mex に切り替えてた。
mex で高速化できそうなところは一通り行ったが、これによって、
105.8秒かかっていた計算が 40.8秒まで短縮された。

mex にするのも単純に行えばいいわけではなく、アルゴリズムとデータ構造を検討する必要がある。
たとえば、同じ計算を行うにしても
[A] 2重ループだけど、読み込むメモリ空間が連続している
[B] 1重ループだけど、連続していないメモリ空間を読むことがある
の場合、実際に動かしてみないと優劣は判断しづらい。（特に [B] は、「どれだけ連続していないか」に依存しやすいため。）
このあたりのバランスが難しい。
今日のプログラムでは [B] のほうが速く、理由としては[A]の内部ループが比較的短いループだったことによるようだ。

今日の作業内容：mex 高速化 4h 論文読み込み 2h
今日のランチ： つかさ カンパチまかない丼
明日の予測作業時間： 5h

Matlab を mex で高速化

SNL の計算の場合、行列の大きさ、特に行数が 2 or 3 と固定されているので、これを利用すると Matlab で行っている計算の一部を mex つまり C or C++ or Fortran で高速化できる。

Matlab の行列演算は基本的に lapack, blas なので、行列演算自体を mex で呼んでも高速化できないが 行数が固定されているので、これを利用して高速化できるのである。

たとえば、行列 X の各列ベクトルのノルムを求めるには、
y = norm(sum(X.*X))
となるが、
X の行数が３と固定である場合には、C++ で
for (j=0;j<n;++j)  y[j] = sqrt(X[3*j]*X[3*j]+X[3*j+1]*X[3*j+1]+X[3*j+2]*X[3*j+2]);
のよう直に記述すると高速にできる。
（３をループにしないのが効いている。）

これらの方法を使って SNL の計算の 50 % 程度を短縮できている。
あともう少し短縮できるはずなので、それをどうするかが検討するところである。

今日の作業内容：mex 高速化 5h
今日のランチ：ちゅらさん　島豚しょうが焼き
明日の予測作業時間：5h

xmind でマインドマップ

論文などを読み込んだときにどういった内容だったかを忘れてしまうことがあるので、マインドマップにして取っておくようにしている。
マインドマップのソフトはいくつかあるが、 xmind はかなり綺麗にマインドマップを作れるため便利である。
有料版もあってフリー版の場合は Word への出力などができないが、マインドマップの基本的な部分はできるので、シンプルな使い方だけであればフリー版で十分である。
また、フリーソフトの freemind のファイルへの出力、freemind のファイルの読み込みもできるので、いざとなったら freemind で 他のフォーマットに出力する、という手もある。
xmind はポータブル版があるので、まずはポータブル版で試してみて、本格的に使うようになったらインストール版を使うこともできる。

今日の作業内容：論文読み込み 5h
今日のランチ：しなの 冷やしたぬきうどん
明日の予測作業時間：5h

論文読み込み

SDPARA の論文の校正は昨日で一段落であるため、今日は SIAM Opt のときに知った論文を読んでおいた。
Optimizatoin Methods & Software に投稿中の論文で、論文の証明で一か所だけ穴があるようだが致命的なミスではないようだ。
この論文のベースになっている論文があって、これをスペシャルケースで高速化している、という内容である。

実は、ベースになっている方の論文をまずは読んだがよく分からなかったので、こちらの論文でさきに概要をつかんで戻ることにしている。
ベース論文は LP 制約だけなので、これを SDP 制約に拡張することができるかと思うが、ベース論文を引用している論文を検索するとそのような拡張は今まで行われておらず、研究内容としてはありかと考えている。

ほかに似たような研究をしているのがどのようなものがあるかを探し始めたが、Wolkowicz の学生が survey を行ったものが幅広く情報を集めているようなので、これをまずは手始めに読んでいくことにする。

今日の作業内容：論文読み 5h
今日のランチ： シッダルータ　チキンカレー
明日の予測作業時間：4h

なぜ多項式最適化はダメになったのか

SIAM Opt に参加したころから少し考えているが、ここ数年で多項式最適化の SDP 緩和による研究が急に少なくなってしまったように感じる。
Lasserre は ISMP でも賞を取ったし、多くの研究者が多くの論文を書いていた。
しかしながら、そのほとんどの研究者は論文を書いただけで他の研究テーマに移ってしまったようだ。
多項式最適化の SDP 緩和の研究は理論的な枠組みが複雑であったぶん、このまま研究者がすくなくなると、論文の数は多くても研究の蓄積は活用できないという状況に陥ることも考えられる。

もちろん、研究テーマにも流行りや廃れがあるのであるが、その一方で Mixed Interger Programming や 一般的な Nonlinear Programming はコンスタントに研究発表があったり、などテーマによっても違う。
なぜ多項式最適化ではダメだったのか、そこがよく分からない。

今日の作業内容：SDPARAの論文の校正 3h　+ 論文読み 3h
今日のランチ：つかさ　生サーモン照り焼き
明日の予測作業時間： 5h

NO_AFFINITY

SDPARA,SDPA ではマルチスレッドで高速化しているが、BLAS の構成のときに設定を誤るとこの効果が得られなくなる。
GotoBLAS2, OpenBLAS2 の場合には、
$ make BINARY=64 NO_AFFINITY=1
と AFFINITY を使わないように設定する必要がある。

ただ、AFFINITY を使わないとなぜ高速になるかは今一つよく分かっていない。
たとえば、SDPA でマルチスレッドを使っている間は BLAS を使わない計算をしていても（具体的に言うとF1,F2,F3 のうちの F3 だけを利用していても）、なぜか NO_AFFINITY の影響を受ける。
正確には OMP_NUM_THREADS の部分かもしれないが、NO_AFFINITY = 1 を設定しないとOMP_NUM_THREADS=1 のほうが OMP_NUM_THREADS=4 よりも F3 が高速に実行される。
両方とも 4 スレッドで計算はしているのだが、OMP_NUM_THREADS=4 はほとんどの計算がひとつのスレッドに集中している様子だ。

あと、SDPARA については MUMPS を利用しているが、MUMPS は OpenMPI との相性が良くないようで libpthread.so が segmentation fault を起こすことがある。
この場合には OpenMPI に代わって、MPICH2 を利用することになる。
MUMPS の FAQ
http://graal.ens-lyon.fr/MUMPS/index.php?page=faq#3
を見ると、MPICH, LAM_MPI は載っているが OpenMPI は載っていないので OpenMPI ではテストしていないことも考えられる。

今日の作業内容：SDPARA 数値実験 4h
今日のランチ：ちゅらさん へちまの味噌煮
明日の予測作業時間：5h

RHEL5.5 から Scientific Linux 5.6 に乗り換えるには

RHEL(Redhat Enterprise Linux) から RHEL 互換 Linux への乗り換えだが、今までは CentOSが主流だったが、CentOSの開発状況が芳しくないことから、今回は Scientific Linux へと乗り換えることにした。

Scientific Linux も RHEL 互換なので、再起動することなく乗り換えることができる。
詳しくは以下の手順となる。

# cp /etc/redhat-release /etc/redhat-release.orig
# rpm -e --nodeps redhat-release-notes redhat-release yum-rhn-plugin redhat-logos
# wget http://ftp.jaist.ac.jp/pub/Linux/scientific/5x/x86_64/SL/sl-release-5.6-1.x86_64.rpm http://ftp.jaist.ac.jp/pub/Linux/scientific/5x/x86_64/SL/sl-release-notes-5.6-1.noarch.rpm http://ftp.jaist.ac.jp/pub/Linux/scientific/5x/x86_64/SL/redhat-logos-4.9.16-2.sl5.6.noarch.rpm
# rpm -ihv sl-release-5.6-1.x86_64.rpm sl-release-notes-5.6-1.noarch.rpm redhat-logos-4.9.16-2.sl5.6.noarch.rpm
# rm sl-release-5.6-1.x86_64.rpm sl-release-notes-5.6-1.noarch.rpm redhat-logos-4.9.16-2.sl5.6.noarch.rpm
(yum.conf だけうまく上書きできないので、バックアップをとっておいて
  --force で上書き)
# cp /etc/yum.conf /etc/yum.conf.original
# wget http://ftp.jaist.ac.jp/pub/Linux/scientific/5x/x86_64/SL/yum-conf-5x-1-9.SL.noarch.rpm
# rpm -Uvh --force yum-conf-5x-1-9.SL.noarch.rpm
# rm yum-conf-5x-1-9.SL.noarch.rpm
# yum clean all
# yum update yum
(以下が本格的な切替え)
# time yum update
# yum clean all
Redhat のサブスクリプションが切れていることのエラーが出るので、
# vi /etc/yum/pluginconf.d/rhnplugin.conf
enabled = 1 を 0 に設定
最新の情報に更新する
# yum update
OS が切り替わったことを確認
# cat /etc/*release
Scientific Linux SL release 5.6 (Boron)
電源投入などの起動時の kernel 選択に SL 由来のものがあることを確認
# cat /etc/grub.conf  | grep SL
title Scientific Linux SL (2.6.18-238.12.1.el5)

以上で乗換えが終了する。
今回、参考にしたのは、
http://mogtechblog.blogspot.com/2011/03/rhel5centos5.html
https://www.scientificlinux.org/documentation/howto/upgrade.5x/view?searchterm=yum update
のサイトである。

今日の作業内容：SDPARA 数値実験 5h
今日のランチ：しなの　野菜天せいろ
明日の予測作業時間： 4h

SNL の論文を数値実験で確認してみた

昨日まで読んだ論文をもとに小さめの数値実験をしてみた。Matlab のコードでだいたい１５０行程度。
数値誤差の点からいうと、あまり芳しくはない。

元論文がひとつひとつのノードに対して順番に計算を適用するようにしているのに対して、今日試してみたのは、全部のノードをまとめて計算しているので、その差が出ている可能性もある。
複数の距離情報を一度に更新しようとしているので、そのあたりに無理がでていることが考えられる。
いずれにしても、gradient の部分は、最初の数反復が決定的に重要なので、そこだけは精度良く行って、あとは軽い計算にするという手も考えられる。

もう少し検討してみよう。

今日の作業内容：SNLの数値実験 5h
今日のランチ：つかさ ネギトロ丼 \700
明日の予測作業時間：4h

SNL の論文、ようやく解ってきた

一昨日から読んでいる論文だが、ようやくどのような計算をしているかがわかってきた。
自分が変数の意味を勘違いしているところもあったし、誤植で符号が逆になっているところもあったりで、計算式の意味を見出すのが大変だったが、だいたいの見通しが立ったところだ。
（論文の著者にも、「このあたりが誤植のようだ」というメールを送っておいた。）

ただ、この論文では基本的にひとつひとつのノードをベクトルで計算しているので、これをすべてのノードを行列で一度に計算できるのかどうか、計算式を検討してみる必要がある。

今日の作業内容：論文読み 3h
今日のランチ：シッダルータ キーマカレー
明日の予測作業時間：3h

導出過程がよく解からず

昨日の論文を続けて読んでいるが、いまひとつ導出過程が解からない。

たとえば、最小自乗法なら
(1) データをフィットさせたい
(2) 自乗誤差を最小化する
(3) 正規方程式を解く
のように、数式に持ち込む際に(2)のようなことが起こるが、今読んでいる論文では(2)がなくて(3)になっている。
雰囲気から察すると、たぶんあっているようにみえるのだが、もう少し確認に時間を費やしてみようと考えている。

今日の作業内容：SDPARA クラスタチェック 2h + 論文読み 2h
今日のランチ：白身魚フライと春巻きの弁当
明日の予測作業時間 4h

そのアイデアはなかった

SNL の計算の場合、距離の情報に noise が入ることがよくあるが、通常は noise が入っていても与えられた距離情報にあうように位置を決定してしまう。
今日読んだ論文では、位置を決定することと距離情報の修正を交互に反復することで精度を高くする方法が取り上げられていた。
input についても修正をする、というのは今までに考えたこともなかったし、これまでに読んできた論文にもなかったアイデアである。
これがどの程度利用できそうか、検討してみたい。

今日の作業内容：SNL の論文読み 2h
今日のランチ: 食堂 さらさらトン茶, 五目ひじき, ほうれん草のナムル
明日の予測作業時間：4h

maximal cliques の clique 同士は勝手には merge できない

SDP を細かい対角ブロックに変換するときに、 chordal graph を用いて maximal cliques を生成し、この cliques を用いて変換する方法がある。
このときに、clique があまりに細かく分類されたときには、clique tree に従って clique 同士を merge する。つまり、clique tree で隣同士の clique が merge される。

ここで、隣同士ではない clique を merge するとどうなるか調べてみたが、この場合はうまく変換できないことがわかった。
たとえば、cliques が {1,2},{2,3},{3,4},{4,5},{5,6} となっているとき、これらを順につなぐと clique tree が作れるし、これらは maximal cliques になっている。
このときに、{1,2},{5,6} を {1,2,5,6} に merge すると、maximal cliques でなくなってしまう。
(2,3,4,5 が 4 の長さの cycle になってしまうため)

ちなみに、clique  を merge できる簡単な場合は
(1) clique tree で隣同士
(2) clique tree で間にひとつだけ clique がある同士
であるが、他にもいろいろな条件で merge できる場合がある。

今日の作業内容：clique の性質調べ 4h + trilateration 1h
今日のランチ：らく　マグロのづけ丼
明日の予測作業時間：5h

OpenMPI と libtool

SDPARA を実験用にコンパイルし直しているが、まだうまくいっていない点がある。

まず、intel コンパイラと gcc コンパイラがあるときには intel コンパイラのほうが性能が出やすいので intel コンパイラでコンパイルするが、intel コンパイラだと動作が不安定になることがある。（データの転送に時間がかかったりする。）
このときには gcc で統一してコンパイルを行うのが安全策だが、intel コンパイラのライブラリが ldconfig で登録されていると、gcc と intel が混在してより不安定になる。
このことは、例えば
$ ldd sdpara
とするとわかる。
ldconfig に登録されているものは
$ /sbin/ldconfig -p
で出力される。

ldconfig はルート権限がないと修正できないので、LD_LIBRARY_PATH で対応することになる。
ただし、OpenMPI の中に含まれている libtool のスクリプトは ldconfig の情報を利用してしまうので、注意が必要である。

OpenMPI の場合の作業は、
1. configure を実行
2. grep で ldconfig から持ってきたパスの部分を削除 。libtool, config.h などの複数ファイル,ディレクトリにあるので注意。
$ grep -r -l (ldconfigのパスで不要なところ) *
として探す。
3. make
4. grep でもう一度確認してバイナリファイルに含まれていないかをみる
5. make install
6. LD_LIBRARY_PATH を設定
となる。

あと、OpenMPI で infiniband, Ethernet が両方ついているときには、
$ mpirun  --mca btl ^openib --mca btl_tcp_if_include eth0
とすると、Ethernet を明示的に設定できる。
また、
$ mpirun -np 2 ./cpi.exe
で gdb をかけるのであれば、
$ gdb mpirun --eval-command="run -np 2 ./cpi.exe"
とすれば可能であり、valgrind なら
$ mpirun -np 2 valgrind ./cpi.exe
である。


ここまでいろいろと調べてみたが、Sparse Cholesky factorization の解析のときに pthread がセグメンテーションフォルトを起こしてしまう。
valgrind で調べると、OpenMPI 1.5.3 はかなりメモリーリークを起こしているようなので、あとで OpenMPI 1.4 系列の stable 版に切り替えてみることとする。

今日の作業内容：SDPARAコンパイル 5h
今日のランチ：信華園 レバー野菜炒め
明日の予測作業時間：5h

uninterruptible sleep

SDPARA の数値実験を夜に行うために、昼間のうちにコンパイルと小さい問題での動作確認をしているが、このときに SDPARA のプロセスが uninterruptible sleep で残ってしまうことがわかった。
通常のプロセスだと kill -KILL で強制終了できるが、この状態におちいると kill -KILL も無視してのこってしまうようで、OSを再起動させるしかないようである。

今日の作業内容：CV作成 2h + uninterruptible sleep の解除方法があるか確認 3h
今日のランチ：シッダルータ　ベジタブルカレー
明日の予測作業時間：3h

SDPARA の実験、なんとかできそう

電力関係でできるかどうかわからなかったSDPARAの実験だが、いろいろと配慮してもらったおかげで、できるようになった。
電力が集中する昼間を避けるために夜に実験することになるが、配慮してもらった分もあるので、できるだけ手早く片付けてしまいたいところだ。

あとは、SNLの計算について。
gradient method のところで、一部を修正すると違った用途に使えるのでその修正をしようと思うが、この部分は自分で書いたわけではないので、まずはどのようにプログラムが書かれているかを見ることにする。

今日の作業内容：SDPARA の実験の準備 2h  + SNL の計算関係 3h
今日のランチ：たちばな あじのお寿司
明日の予測作業時間：4h

SDPARA の実験結果の整理

論文のために、この前の小さいクラスタでの実験結果を整理している。
それぞれのスレッドで、それぞれの反復での計算時間を 3次元プロットしようとしたが、こういったものは Excel だとプロットできないようで、Matlab の plot3 を使ってプロットした。
また、単色だとデータを見づらいので colormap を使うことで色を段階的に変化するようにもしている。

整理してみると、やはり大きなクラスタとは違った動きをすることがあり、この変化が起こる理由を調べる必要がありそうだ。
ただ、電力の抑制が始まっている関係で、クラスタをいつ利用できるかわからないので、そのあたりも検討が必要である。
SDPARA の校正は、この小さいクラスタを除いてはほぼ終わっているので、このクラスタに電力を回してもらうようにお願いして先に片付けてしまうのもいいのかもしれない。

今日の作業内容：SDPARA 校正 2h + CV 更新 1h + SNL 計算 2h
今日のランチ：角笛 トマトソースチキン
明日の予測作業時間：4h

Google で英語表現の検索

Google のワイルドカードなどを使うと英語表現の検索に利用できる。
たとえば、confidence などがどう使われているかは

"we have confidence *"

のように検索できる。
他にも

"we have confidence *" site:springer.com

とすると、springer の検索結果に絞り込めるので、論文やアブストラクトに載っているものがヒットしやすい。（ただし、springer のサイトは同じ情報が複数個所のっていることがあるので、そのあたりをうまく見極める必要あり）

あと、google fight を利用すると、たとえば
"occupy most computation time" と "consume most computation time" のどちらがよく利用されているか、などを判断できる。
この場合は、consume が１０倍程度使用頻度が高い。

今日の作業内容：SDPARA 校正 3h + CV 作成 2h
今日のランチ：つかさ　かんぱちまかない丼
明日の予測作業時間: 5h

英語の難しさ

SDPARA の論文の校正で Introduction だけ英語を見てもらったが、やはり英語の難しさを痛感する。

たとえば、「計算時間の大部分を部分Xが占める」というときに、
The X part occupies most of the compuation time.
のように occupy を使って書いていたが、ここで occupy はダメらしく、consume などにするほうがよいとのことであった。
どうやら主語との関係らしいが、occupy は行動する主体でないとダメなので「計算」などでは動詞に使えないということである。
ただし、ジーニアスなどを参照するとこのような occupy の使い方もアリなようにも見ることができるので、さらに難しい。

いずれにしても、まだまだ勉強が必要である。
今度応募しようと思っているところも（無謀にも）海外であるため、やはり英語は必要そうだ。

今日の作業内容：英語の校正 2h + SNL のプログラム 2h
今日のランチ：らく　焼き魚定食
明日の予測作業時間：4h