簡単そうに見えて、とても難しい

今日は、簡単そうに見えて、とても難しい問題に突き当たった。

「頂点数 n, 枝の本数 m のグラフで、multi edge があるかどうかを判断するのが O(m+n) でできるのか」

という問題である。multi edge とは、枝の両端が同じ頂点、つまり、並行している枝のことである。
たとえば、(a,b) で枝が a と b にあるとしたときに、
(1,4), (2,5), (3,4), (2,4), (2,5), (1,3), (1,5)
などとあったときには、(2,5) が２本あるので、 multi edge である。

最初は、頂点の番号でソートすれば簡単だと思ったのだが、それでは O(m+n) にならない。
O(m+n) なので、以下の２つは使えない。
1. ソート（ O(m log m) か O(n log n) となり、O(m+n) を超えてしまう。）
2. 頂点同士のペアで調べることができない (２重の for になって O(n^2) になるため。）

ソートできないと、配列中に同じ値が存在するかどうかを調べるのが線形時間でできるのかどうか解からない。(これが最大のネックになっていると思う)

論文には、multi edge の探索を内部的につかって、全体としてO(m+n) になる、と書いてあるので、これはO(m+n)になるはずなのであるが、さっぱり解からない。



今日は６時間ぐらいかけて、論文の２ページぐらい読み進んだ。
この論文、はたして読み終えることができるんだろうか？

読むのが遅くなっている理由として、必要な事項が足りないことが多すぎる、などがある。
たとえば、「頂点 v について成り立つ」とあるのに、「特定の条件を満たす v について成り立つ」という「特定の条件」が暗黙のうちにかかれていて、これを推測しないといけない。
あと、文章の内容とexampleの図があっていないので、それもどちらが正しいのかを推測しないといけない。

とりあえず、こつこつと読み進めよう。

今日の作業内容: 論文読み 6h
今日のBGM: マクロスF OST [1-2], FF12 OST [1-2]
今日のランチ: いろは 豚汁定食
明日の予測作業時間: 2h

グラフ理論の論文、再挑戦

今日は、まず昨日ダウンロードした Ubuntu 10.04 RC2 amd64 server を vmplayer でインストールできるか挑戦。
結果としては、grub,grub2,lilo がインストールできずに失敗する。
まだ、RC2 なので、そのうちに修正されると考えられる。

あとは、グラフ理論の論文を再読しはじめた。
今回で最初のあたりは５回目ぐらいだが（途中でなんども挫折しているので）、理解が進むと誤植がかなりあることが解かってきた。
読んでいる論文は SIAM J Computing だが、SIAM であっても査読が行き届いているものとそうでないものがあるようで、注意が必要そうだ。

いずれにしても、少しずつ理解できてきたので、まだまだ頑張っていこうと思う。
明日は、この続き。


今日の作業内容: Ubuntu 1h + グラフ理論 2h
今日のBGM: 電脳コイル OST [1-2]
今日のランチ: つかさ サーモンハラス塩焼
明日の予測作業時間: 6h

Ubuntu 10.04 にしてみた

今日は、どうも体のあちこちが疲れていて、調子が出ないので、文章を書いたりプログラムを作ったりは明日以降に延期。

とりあえず、数値実験がきちんと動いていることは、確認済。
ただ、このペースだと、〆切に間に合うかどうか、ちょっと解からないので、問題数の変更なども必要かもしれない。

ということで、ここまでを踏まえて、Ubuntu を 9.10 から 10.04 に試しにアップグレードしてみた。
アップグレードするには、
$ sudo update-manager -d
だが、なぜかレポジトリの読み込みに失敗するので、jp.archive.ubuntu.com からアーカイブミラーサイトを変更した。
update-manager の左下の詳細から、いろいろと変更していたら、あちこちのアーカイブミラーからどれが一番速いか自動的に探索するのがあって（詳細をメモし忘れた）、それに従ってミラーサイトを決定。
あとは、アップグレードに成功。

ただし、いろいろと不具合も出ている。
1. vmplayer のユニティができなくなった（表示はするけど、各ウィンドウが反応しない。vmtools の再インストールもダメ）
2. Adobe Reader がインストールできない
これらの不具合が一般的なものなのか、単純に自分のところだけなのかは不明。

あと、Gnome のテーマをいじって Windows 7 風にすることができるらしいので、これも挑戦してみたが、うまくいかず。
Gnome のテーマの設定のしかたから勉強したほうがよさそうだ。

とりあえず、アップグレードはここまでにしておき、次は RC2 の DVD から vmplayer にインストールしてどうなるかを見てみることにする。


今日の作業内容: Ubuntu 5h + 数値実験 1h
今日のBGM: EVA OST [1-3]
今日のランチ: 味庵 白身魚の黒酢ソース
明日の予測作業時間: 6h

Type P インストール終了と原稿の調整

先週から続けていた VAIO Type P については、必要そうなものは一通りインストールした。

ATLAS については、何回かチャレンジしてみたが、うまくいかなかった。
そもそも Atom では ATLAS が unknown と判定されるところからも、ATLAS は Atom を認識できていない。
もちろん、数値計算に向くとは思えない Atom で ATLAS をコンパイルするのは少数派だと考えられるので、大きな問題ではない。
ただし、GotoBLAS2 は Atom をきちんと認識して、コンパイルがすんなりと通る。

Ubuntu 9.10 on vmplayer 3.0 on VAIO Type P では、
SDPA, SDPARA を実行することは可能である。

ちなみに、Type P は CPU がファンレスなため、驚くほど静かである。
HDD モデルなので、HDD にアクセスしているときは音が解かるが、SDD モデルならば一層静かに違いない。
ただし、熱は外側に伝導で逃しているだけなので、長時間ひざの上に置くなどして作業すると低温火傷するかもしれない。（懐炉みたいに温かくなる。）
あと、600g と軽い。



あと、今日は原稿をスタイルファイルにあわせての変更を行った。
参考文献の論文リストを調整するのに手間取り、３時間程度かかった。

参考文献の論文リストは、bibtex などでも管理できるのであるが、bibtex では個々の学術雑誌のスタイルにまで対応しきれない。
特に、ファーストネームのイニシャルがラストネームの前に来るか後ろに来るか、などの対応が難しい。
将来的には、DOI を入力すると自動的にフォーマット化するような仕組が整備されると思う。
データベースさえあれば、あとはシェルスクリプト程度で作ることができる。
当然、データベースを作るのがもっとも大変である。

なお、SDPARA の論文の DOI は
http://dx.doi.org/10.1016/S0167-8191(03)00087-5
である。

今日の作業内容: Type P インストール 2h + 原稿調整 4h
今日のBGM: DEWPRISM OST [2], FF9 OST[1-2]
今日のランチ: いろは 豚ヒレカツと牛肉コロッケ
明日の予測作業時間: 6h

グラフ理論ライブラリ、まだまだ

今日は、午前中に文章の構成を考えたり、数値実験用のデータ作成を行ったりした。

午後に、グラフ理論用のライブラリを少し書き足し。
あとは、ホームページにインストール方法や、使いかたを書きはじめる。
今回のライブラリは、インストールは実質
$ make lib
で終了である。いたって簡単。
あと、ドキュメント類については、いろいろと分散すると統一性がなくなるので、ユーザが見れるドキュメントはすべて HTML に統一。

基本的なルールを決めたら、それぞれの関数はプログラムを組むひとが各自のディレクトリでできるだけ自由に使えるようにしたい。
コンセプトは、

ユーザも開発者も、simple & consistent

である。
グラフ理論の理論的な勉強をのぞけば、プログラムの部分は１時間程度で理解できるようにしたいし、１時間で理解できたことが広範囲に応用できたほうがいい。


今日の作業内容: 構成を考える 1h + データ作成 2h + ライブラリ作成 3h
今日のBGM: 小松未歩 Best [1-2], MADLAX OST [1-2], DEWPRISM OST [1]
今日のランチ: らく 焼魚定食
明日の予測作業時間: 5h

グラフ理論用ライブラリの作成と SDPA ベンチマーク

今日は、昨日の思い付きのままに、グラフ理論用ライブラリを作り始めてみた。
まずは、最短路問題をダイクストラ法でプログラムを作成し、ライブラリにはどのようなファイルが必要かを特定することとした。

BLAS/LAPACK の場合には、出力の行列の規模が最初から解かっているので、ユーザがそれを確保すればOKだが、グラフ理論の場合、計算してみないと解からない。
例えば、最短路であれば、最短路を出力するためには、最短路の頂点数だけの配列が必要だが、その頂点数は計算しないと解からない。
これをどのようにクッションを入れるか、が難しいところだ。

あとは、関数ごとにディレクトリを別にすることで、他のディレクトリから独立してプログラムを組むことができる。
それぞれのディレクトリには、Makefile を配置し、make lib により全体としてのライブラリ(lib???.a) に ar で組み込む仕組を導入した。
これによって、一番上の Makefile は各ディレクトリに入って make lib を実行するように書くだけでOKとなる。
もちろん、サンプルプログラムや、マニュアル類もそれぞれのディレクトリごとに置く。
つまり、それぞれのディレクトリで、
$ make lib
$ make sample
$ make run_sample
が実行できるようにしている。
このようにすることで、関数ごとに違うプログラマが実装しても全体としての調和を維持することができる。



今日は、他に Ubuntu on vmplayer on Type P で SDPA をインストール。
ATLAS のコンパイルは、configure に失敗していて上手く行っていなかったので、GotoBLAS2 を使ってのインストール。
明日あたりに、ATLAS のコンパイルに再挑戦したい（ATLAS のコンパイルは６時間以上かかるため。）

実際に実行して、Type P(Atom Z550, 2.0GHz) と Xeon X5365(3.0GHz) で比較してみた。
control8 Atom 204.75 秒, Xeon 18.18 秒 (11.1倍)
arch0 Atom 8.32 秒, Xeon 1.12 秒(7.42倍）
とかなり違いが出た。
基本的には、Xeon のPCと比べると Type P は 10 倍程度遅い。
ちなみに、ユニティを使っていると、arch0 が 8.32 秒から 11.43秒に遅くなる。
やはり、ユニティは CPU 消費が大きいようだ。

ついでに、SDPARA もインストール。
なお、Ubuntu の場合は、/etc/hosts に不自然な点があるので、rsh を実行するときには注意が必要。
たとえば、hostname を mypc1 にすると、localhost は 127.0.0.1 であるが、mypc1 は 127.0.1.1 になってしまう。
したがって、xinetd で　only_from をかけたときに 127.0.0.1 だけだと、挙動がおかしくなる。
この場合は、/etc/hosts で localhost も mypc1 も 127.0.0.1 に割り当てたほうがよい。
なお、xinetd の各設定は、Vine からコピーした。xinetd で rsh を動かすときには、rsh-server パッケージではなく、rsh-redone-server パッケージをインストールした。

あと、iptables でポートが閉じられているはずなのだが、よく解からないうちに動くようになってしまった。一度
$ sudo iptables -F
で全部開放したのが効いたのかもしれないが、たしか iptables は特別な設定をしないと Ubuntu を再起動したときに元に戻るはず。ただ、Ubuntu を再起動しても、なぜか SDPARA はきちんと動く。
不思議だ。

今日の作業内容: ライブラリづくり 4h + Ubuntu 3h (一部並行作業）
今日のBGM: スカイ OST[1-2], MADLAX OST [1-2], FF5 OST [1-2]
今日のランチ: シッダルータ ほうれんそうとチキンのカレー
明日の予測作業時間: 3h

グラフ理論の信用度と Ubuntu on vmplayer on Type P

最近、グラフ理論の論文を続けて何本か読んでいるのだが、どうにも信用できないことが多い。
まず、あいまいな表現が多くて、実際に実装するできない記述が目立つ。
どうやら、査読が甘いらしく、きちんと動かないアルゴリズムのままで論文になっている。
ある論文は、他の著者の論文で修正が入っていたりする。

たまたま運悪く、間違いの多い論文にばかり当たっているのであれば、それは仕方ないのだが、グラフ理論についてはプログラムとして公開されているものが少ない印象があるのも気になる。
本格的なのは LEDA と Lemon ぐらいしか簡単には見つからず、あとは Spanning Tree など個別に組まれているものに限定されるようだ。
したがって、「Spanning Tree を使って、このアルゴリズムは設計されている」と論文でなると、Spanning Tree から実装する必要がある場面が出てきてしまう。

行列演算については、積や基本的な分解はプログラムとしてはとりあえずは BLAS/LAPACK に任せればいいのであるが、グラフ理論の場合、Spanning Tree のような基礎的なものを網羅したライブラリが少ないようだ。
BLAS のように標準的なインターフェースを整備して、実装を整備すれば、利用価値は高いのかもしれない。


あと、今日は Ubuntu on vmplayer on Type P の続き。
今日の作業内容は、以下のとおり
1. Windows 7 での ctrl<->caps 入れ換え (ctrl2caps)
2. xkeymacs のインストール
(以下は Ubuntu on vmplayer)
3. XDG のディレクトリを変更してホームディレクトリを整理
(~/.config/user-dirs.dirs で、
XDG_DESKTOP_DIR="$HOME/デスクトップ"などを
XDG_DESKTOP_DIR="$HOME/.XDG/デスクトップ"に変更して、
~/.XDG/デスクトップを mkdir しておいて、再ログイン）
4. git をインストール
5. ~/.bashrc を Vine を参考にして修正
6. ~/.emacs/init.el も Vine の ~/.emacs*.el を参考にして修正
((setq inhibit-startup-message t) とすると、最初のメッセージを
表示させないようにできる。
また、日本語入力は anthy のほうが安定しているので、
Ctrl-o, Shift+space などを anthy に切替え）
7. ibus の切替えを Ctrl+space から Shift+space に変更
(emacs で範囲選択ができなくなるため）
8. gconf-editor で gnome のキーバインディングを Emacs に
9. SDPA インストールに向けて、gfortran, mpich2, autoconf を
インストール
10. ATLAS のコンパイル

今日は、ATLAS のコンパイルまで。これが７時間かかっても終了していない。
さすがに Atom Z550 で vmplayer を使ってATLAS をコンパイルするのは大変なようだ。
ちなみに、Type P は 30 分触らないと、コンパイル中でもスリープしてしまうので、
「タスクバー」の右の方にある「電源」から電源プランを変更し、電源に接続しているときはスリープさせないように変更した。

今日の作業内容: 論文読み 5h + Ubuntu インストール 3h (一部、並行進行）
今日のBGM: 電脳コイル OST [1-2], FF6 OST[1-3]
今日のランチ: らく さけイクラ丼
明日の予測作業時間: 6h

Type P な一日

今日は、一日まるごとかけて、Type P の初期設定。

1. Windows Update（これが終わるまで、約１時間３０分）
2. セキュリティソフトインストール
3. Office インストール
4. Windows Update (Office Update も含む）
5. リカバリーディスクの作成（DVD１枚作成に、約１時間）
6. vmplayer のインストール
7. Ubuntu のインストール（１時間３０分かかって、アップデートマネージャ中）

今日の作業はここまで。
Type P が SSD でなく HDD(80GB) のためなのか、Ubuntu が非常に遅く感じる。
ただし、現状の Ubuntu は、10.04 が出るまでのつなぎなので、今のうちに Ubuntu ではどういったトラブルがあるのか把握しておきたい。

今日で大まかな作業は終わったので、明日は論文読みと並行して SDPA, SDPARA のインストールに挑戦してみよう。

今日の作業内容: Type P 6h
今日のBGM: なし
今日のらんち: つかさ　生サーモン照り焼き
明日の予測作業時間: 6h

Ubuntu & Vine on vmplayer

今日は、予定を少し変更して、vmplayer で Ubuntu と Vine を比較。
やはり、Vine のほうが軽くて、日本語が問題なく実行できる。
ただ、gcc などを含めると Ubuntu のほうが新しい。

Vine でインストールしたところから、synaptic で Ubuntu のリポジトリにアクセスできたら、ディストリビューションとしては最高のできになると思う。

ところで、ずっと以前に vmplayer 2.5 でインストールしてあった Fedora 9 だが、vmplayer 3.0 でも起動できた。
この場合、vmplayer 3.0 で起動したあとで、vmware-tools を再インストールすると、マウスなどもきちんとボーダーを越えられる。
ただし、ユニティはそのままでは使うことができない。
これは、vmplayer 2.5 の仮想ディスクが Workstation 4.x 相当とみなされるためである。
vmplayer 3.0 でユニティを使うには、vmware-tools をインストールしたあとに一度vmplayer を終了しておき、vmx ファイルをメモ帳で

virtualHW.version = "3"
を
virtualHW.version = "7"
にする。

これで、vmplayer で開くと、Workstation 6.5-7.0 の仮想ディスクと見なされ、ユニティを使うことができた。
（ただし、ユニティはうまくいかないときがあって、Vine 5.0 でも別のPCではうまくいかないのに、今回はうまくいく、などよくわからない点がある。両方のPCともに、Ubuntu の場合にはユニティは動いている。）

あと、今日はグラフ理論の論文読み。

今日の作業内容: 論文読み3h + インストール 5h (途中、並行作業）
今日のBGM: EVA OST [1-3]
今日のランチ: らく 生姜焼定食
明日の予測作業時間: 5h

Type P がやってきた

新しい Type P がやってきた。
本格的に Windows 7 マシンを触るのは初めてである。
今日は、マニュアルを読んでみた。
明日は、電源投入からバックアップまでになると考えている。

原稿作成は、図などを調整。
ただ、文字数が限界を突破していることが判明。
あとで削除する必要があるが、数値実験が終わってからの調整になりそうだ。
数値実験は２月いっぱいでは終わらないかもしれない。

今日の作業内容: 原稿作成 4h + マニュアルチェック 1h
今日のBGM: FF12 OST [1,2,4]
今日のランチ: 新華園　高菜チャーハン
明日の予測作業時間: 6h

原稿準備、つづき

今日は、午後に原稿準備の続きを開始。

２時間程度書き足して、ほぼ原型が完成。

ただ、まだまだ図は入ってないし、数値実験も進んでいないし、変更の可能性が大きい。

明日は、図を入れたり、参考文献を調整したり、もうすこし形を整えよう。

今日の作業内容： 原稿準備 2h

今日のBGM: ハウル OST, もののけ姫 OST

今日は、全然進まず

今日は、いろいろと仕事があって、研究は進まず。
まぁ、今日の仕事はとても重要なことだったので、研究が進まない、というこんな日があってもいいと思う。
（予想外の雑務がなければ、少しは進んだかも。）

明日からは、心機一転、頑張らねば！！

今日の作業内容: とくになし
今日のBGM: とくになし
今日のランチ: VIE DE FRANCE ロングココア、ぶたまんぱん、ソフトサンド（メープル）
明日の予測作業時間: 3h

主双対内点法の実装についての論文

今日は、あまり時間が取れなかったので、かわりに主双対内点法の実装についての論文のメモ。
実際に実装するときになったら、読むべきものとしては、

1. Wright の Primal-Dual Interior-Point Methods （これは本）の１１章
2. On the implementation of an interior-point filter line-seach algorithm for large-scale nonlinear programming, Math. Prog. A, 106(1), 2006

この２つは、教科書的でもあり、実戦的でもあるので、読むべきもの。

今日の作業としては、論文改訂のチェックがメインだった。

今日の作業内容: 論文改訂のチェック2h
今日のBGM: FF7 OST [1-4]
今日のランチ: 四川　麻婆豆腐
明日の予測作業時間: 6h

Math.Prog.Comp. と 原稿準備

今朝、Mathematical Programming Computation の印刷されたものが届いた。
インターネット上では見ることができていたが、やはり本になると印象が違う。
電車に乗っていても読むことができる。

これで、Mathematical Programming には A,B,C がそろったことになる。
A: 通常の論文
B: 大きな会議やメモリアルなど特集系
C: Computation (計算やソフト重視）

次ができるとしたらもちろん D であって、そうすると Discrete のあたりだろうか？

あと、今日は原稿準備に突入。
昨日コピーしてきた論文の論文読みは、もう少しあとになりそうだ。
今回の原稿は、ひさしぶりに日本語なのがよい。


今日の作業内容: 原稿準備 5h
今日のBGM: MADLAX OST [1-2], ポニョ OST
今日のランチ: つかさ 活かんぱちのまかない丼
明日の予測作業時間: 1h

メール整理と論文コピー

最近、メールが HDD に溜ってきており、これをバックアップするのが大変だったので、整理した。
およそ 800MB がすっきりとした。

あとは、論文コピー。さすがに雑誌に載っているのは完全版であって、Figure ももちろん入っていた。
ただ、今日はこれを読んでいる時間がなかったので、木曜日に読もうかと思う。

他に、SNL のプログラムで以前に組んだもの（edge 関係）に bug があるようなので、どこにバグがあるのか調査中。

今日の作業内容: メール整理 1h + 論文チェック 1h + SNL チェック 2h
今日のBGM: 小松未歩 Best [1-2]
今日のランチ: シッダルータ チキンとマッシュルームのカレー (今日はライス)
明日の予測作業時間: 5h

グラフ理論の論文読み、最後の論文

今回のグラフ理論の論文読みでは、今日から読み始める論文をとりあえず最後の一本にして、これでうまく行かなければ、一時撤退にしようと思う。

ある意味背水の陣であるが、背水の陣のおかげか、今までよりも理解できるような気がする。
やはり、研究に気合は大事である。

ただ、この論文、インターネットでダウンロードしてきたものには Figure が入っていない。
やはり雑誌に掲載されている分をチェックして、Figure がないと例が理解しづらい。
月曜日に雑誌からコピーして、それで理解したほうが間違いが少なく、効率的になりそうだ。
したがって、明日は研究はお休みにする。

今日の作業内容: 論文読み 2h
今日のBGM: なし

グラフ理論は難し過ぎた

今日も一昨日に続いて、グラフ理論関係の論文をチェックしてみたが、やはり曖昧な記述が多く、実装に耐えられるものが少ない。
あと、グラフ理論関係のソフトウェアがあまりに見つからないのも驚きである。
オープンソースで使えそうなのは、

LEMON

ぐらいしかなく、他にも商用の LEDA や Mathematica などがあるが(Mathematica をグラフ理論のソフトとみなすかどうか判断に迷うけど）、LEDA と LEMON のいずれにも実装されていないアルゴリズムは簡単には見つからない可能性が高いようだ。

このままでは行き詰まることが解かってきたので、あともう一本だけ読むことにして、それでダメなら、一時撤退にしようと思う。

今日の作業内容: 論文読み 2h
今日のBGM: FF12 OST [1]
今日のランチ: 味庵 白身魚と春雨の四川風
明日の予測作業時間: 5h

グラフ理論と chunk

今日は、あまり時間が取れなかったので、昨日までの論文とは気分転換を兼ねて

The molecule problem: exploiting structure in global optimization, SIAM J. Optim., 5(4) 835-857, 1995

をチェック。
いろいろと書いてあって勉強にはなるのだが、グラフの枝の本数だけの大きさの行列の QR 分解が必要と解かり、これが致命的。
SNL の計算に使ってしまうと、10万 x 2000 といったサイズの QR 分解になることが予想され、計算時間からしても現実的ではないし、数値精度が落ちてしまう危険性もある。

ただ、chunk という概念が導入されており、これは利用価値が高そうだ。

今日の作業内容：論文読み 2h
今日のBGM: FF10 OST [1,2]
今日のランチ: らく 焼魚定食
明日の予測作業時間: 2h

TSUBAME on TV

今日聞いてきたところによると、今日の２３時ぐらいからの News Zero で TSUBAME が出てくるようだ。
ただ、ニュース番組なので、大きな出来事があったら放送されないかもしれない。

今日は、昨日に続いてグラフ理論の論文をチェック。
ただ、どうにも読んでいて、あいまいなところが多すぎることが気になる。
アルゴリズムが複雑なので、査読がきちんと行き届いていない可能性もある。
このまま、この論文にしたがって実装するのは危険と判断し、他の論文も検索。
すると、多くの論文で参照している、もっともベースとなっている論文に誤りがあることを指摘している論文を発見。
ソフトウェアとしてメンテナンスされているものがないので、雲行きが怪しい。

とりあえず、誤りを指摘している論文に書いてあるアルゴリズムを今度はチェックする。

今日の作業内容: 論文チェック 5h
今日のBGM: MADLAX OST [1-2], FF10 OST [1,2]
今日のランチ: らく カキフライ定食
明日の予測作業時間: 1h

論文改訂のチェックと homogenous self-dual

今日は、論文改訂のチェック。
一ヶ所だけ、よくわからないところがあり、そこが大変だったけど、教えてもらったら理解できたのでよかった。

あとはグラフ理論の論文読みの続き。
この論文、一度はダウンロードできたが、今日やってみたら、なぜかうまくいかなかった。これの元になっている論文をダウンロードしたいのだが、できるかどうか解からない。
内容は、ざっと目を通したところ。
実装するにあたって、あと何回か読み直したほうが良さそうだ。

あと、homogenous self-dual を実装したプログラムをもらったので、その数値計算をしてあったメモが見つかったので書いておく。
解いた問題は、control11。

SDPA:
47反復, obj.p 3.1958706, obj.d 3.1958481, p.err 2.32x10^{-9}, d.err 3.08x10^{-8}

self-dual:
49反復, obj.p 3.19586851, obj.d 3.19586839, p.err 1.6x10^{-9}, d.err 6.0x10^{-8}

sedumi:
45反復, obj.p 3.1958717, obj.d 3.1958713, p.err 1.65x10^{-8}, d.err 3.4x10^{-7}

メモをとったときに桁数があっていなかったので、見にくいが、sedumi と同程度の数値精度が出ている。

今日の作業内容：論文改訂チェック 4h + グラフ理論 2h
今日のBGM: EVA OST [1-3]
今日のランチ: 味庵 豚肉と高菜の炒め
明日の予測作業時間: 6h

グラフ理論の論文読み

今日は、午前中にグラフ理論の論文読みをした。
この論文は、1983 年のもので 1973 年の論文のアルゴリズムを視覚的に解かりやすく説明してある、とあるのだが、これがそれでも難しい。(1973年のは２度挫折済み）
一つ一つ絵を書いて、どう動くのかを確認して進めている。

午後は、別の論文の revised をチェック。
こちらは、改訂されたところを中心にチェックしている。

今日の作業内容: グラフ理論 3h + revised チェック 2h
今日のBGM: FF12 OST [1,2]
今日のランチ: 角笛 韓国風ローストチキン
明日の予測作業時間: 6h