2010年12月28日火曜日

2010年仕事納め

今日で2010年も仕事納めなので、少し書いておくことにする。

2010年は論文相当の原稿は3本だったが、やはりそれぞれに時間がかかったので、もう少しコンパクトに進める必要がありそうだ。
特に、数値実験と英語についてである。
数値実験はある程度見積りを立ててから効率的に行う必要がある。SDPA-GMP 関係はかなり時間がかかるので、小さめの問題で先に傾向を知ってから論文用の数値実験を行う、ということをもう少し徹底する必要がある。網羅的に行うことよりも、論文に必要になりそうなところを抑えることを重視したほうがいいのかもしれない。
英語については地道に勉強することにする。
あと、論文の原稿を作成するのには〆切がないため、どうしてもダラダラと進みがちであった。このあたりは仮の〆切を作って、それでコントロールする、など2011年はスッキリとさせたい。

他に内点法関係の勉強については少し前進した感じか。
昨日もメモしたが、やはり内点法に関する論文が多いため、内点法よりも広い枠組のなかで内点法よりも効率的なアルゴリズムを検討する必要があるのかもしれない。

今日の作業内容:論文校正の準備など
今日のランチ: つかさ 生サーモン照り焼き
明日の予測作業時間:3h

2010年12月27日月曜日

内点法について

数値的難しさを計算する数値実験に並行して読み直している論文は、最初は広い枠組で話が進んでいるが、途中から話を簡単にするための制約が入っていて内点法になっている。

この制約がどの程度重要であるか、が難しいところだ。
たとえば、self-concordant は理論的にはきれいな形が導出されるので理論的な論文には使われるが、実際のところは -log(det(X)) を利用するので、self-concordant はあまり実用的な意味がない。
つまり、self-concordant で途中まで話を進めて、そのあとで -log(det(X)) に制約しても計算をする上では問題にはならない。

ただ、論文に書いてある制約を入れると、広い枠組の可能性が狭まるので、その過程で内点法より速いアルゴリズムを失っていることもありえる。
難しいところだ。

そういえば、数値実験については、問題を絞りこんで進めることにした。
問題数を 10分の1 程度にしたので計算時間も 10分の1程度であるが、今年中には終わらないかもしれない。

今日の作業内容:論文読み直し、楕円の計算
今日のランチ:らく うな重
明日の予測作業時間:6h

2010年12月24日金曜日

数値的難しさの計算

以前に作成した gpp の問題で、制約緩和の数値の影響でどの程度数値的に難しい問題になっているかを計算している。

計算プログラム自体はすでにもらってあって、いま計算中であるが、一個の SDP の難しさを計算するのに、その制約の本数分の同じサイズの SDP を解くので、かなり時間がかかる。
どうやら gpp250 の場合、一個の SDP を計算するのに20分かかっており、数値を 10^{-1}から10^{-20} で変更しているので、実質的に 400 分ぐらいかかる。
gpp500 については、もうちょっと絞らないとダメかもしれない。

あと、だいたい解かったことだが、数値を変更するときには、大きく2種類の壁がある。
1. machineEpsilon の平方根 or SDPT3 の閾値 (この2つは似たような値)
2. machineEpsilon
このあたりで振る舞いが変わる傾向がある。
(ただし、gpp 限定の可能性あり)

今日の作業内容:gpp の計算
今日のランチ:らく 焼魚定食
明日の予測作業時間:3h

2010年12月22日水曜日

プロファイリング用に修正

SDPA-GMP, QD, DD と SDPT3, CSDP, SeDuMi をプロファイリング用に修正した。
これによって、それぞれのソフトの結果 (dimacs error や計算時間など) が統一フォーマットに出力されるので、あとは grep や awk で整形すればいいだけである。

SDPA 系列は、どこに何があるか把握しているので比較的簡単だが、やはり他のソフトは修正が難しい。特に、C言語でかかれている CSDP は C++ に慣れた人間からするとハードである。

今日の作業内容:プロファイリング用修正
今日のランチ:たちばな しまあじ
明日の予測作業時間:3h

2010年12月21日火曜日

論文の記号について

最近、以前に読んだことのある論文を読み直しているが、これがなかなかに難しい。
なにが難しいかというと、記号が consistent になっていないことである。
どの意味で記号を使っているかを逐一判断しないといけないのが手間がかかる。

やはり、論文を書くときに記号をどうするかは大事なようだ。
たとえば、 f(x) = 0 と書けば x が解というのがよく使われるパターンだが、これが f(x)=0 と x(f) = 0 の両方が入り混じると読みにくい。

ほかにあったものでは、ギリシャ文字のχとアルファベットの x を使うパターン。
本ならばいいが、やはり手書きでこの2つをきちんと分けて書くのは大変で、あまり好ましくない。

今度論文を校正するときには、こういった点も気をつけたい。

今日の作業内容:論文読み直し
今日のランチ:らく 焼き魚定食
明日の予測作業時間: 4h

2010年12月20日月曜日

SDPA 7.3.4 が Debian/Ubuntu パッケージに

Debian/Ubuntu パッケージを作ろうと思い立って、すでに4ヶ月経ったが、SDPA 7.3.4 が Debian/Ubuntu パッケージに登録された。

Debian については、すでに Debian 6 の準備段階に入ってしまっているので、stable として使えるのは Debian 7 以降になるが、unstable であれば apt-get でインストールできるようになっている。
Ubuntu についても、Ubuntu 11.04 から apt-get でインストールできるようになる。

Debian パッケージの詳細は、
http://packages.debian.org/sid/sdpa
にあり、Ubuntu パッケージの詳細は
https://launchpad.net/sdpa
にある。

注意点として、Debian/Ubuntu パッケージはそれぞれのデフォルトのatlasにリンクされるため、速度面で不利である。行列演算が多いとかなり遅くなる可能性がある。
数値実験の計算時間測定には使えないが、手軽にSDPAをインストールできるようになる。

Debian パッケージをどのようにして apt に登録するか、についてはあまり日本語の資料がないので、これまでに蓄積した Debian パッケージの作り方などのノウハウはそのうちにメモとしてまとめて書き込もうと思う。

今日の作業内容:論文読み
今日のランチ:角笛 ちらし寿司
明日の予測作業時間:6h

2010年12月17日金曜日

QAP の内点がある SDP

今日になってとうとう QAP が内点を持つように制約を変更する方法が解かった。
より正確にかくと、そういう方法を教えてもらった。
Matlab で確認したところ、SDPLIB の QAP を若干修正するだけで、実行可能な内点ができていた。
あとは、この修正でできた SDP がどれだけ難しい SDP なのかを知る必要があるが、これは以前に読んだ論文で measure が提案されている。
今日のうちに、この著者にmeasure 計算のプログラムがあるかどうか、メールを出しておいた。

今日の作業内容:QAP の SDP
今日のランチ:シッダルータ チキンカレー
明日の予測作業時間:4h

2010年12月16日木曜日

QAP relaxation のつづき

今日はまとまった時間がとれなかったため、QAP を内点を持つように変形する方法をもう少し考えた。
またアイデアをもらったので、Matlab で簡単なプログラムを作ってチェックしているが、どこかに間違いがあるらしく、固有値にマイナスが含まれてしまう。
明日に続く展開になりそうだ。

今日の作業内容:QAP の変形
今日のランチ:味庵 白身魚のマーボー煮込み
明日の予測作業時間:5h

2010年12月15日水曜日

QAP relaxation

昨日のグラフ分割問題の制約緩和については、あのあともう少し考えてみたら簡単な数式で内点を表現できることが解かった。
SDPLIB の場合、内点がない問題は他に QAP の系統があるため、今日はこれを確認した。

問題の定式化については、いろいろと教えてもらったので、ほぼ大丈夫であるが、やはり内点を構成するのが難しそうである。グラフ分割と異なってストレートな制約緩和ができそうにないので、内点を先に構成してから、それを満たすような自然な制約緩和を入れるほうが良さそうである。

今日の作業内容:QAP relaxation
今日のランチ: 四川 汁無し坦々麺
明日の予測作業時間:2h

2010年12月14日火曜日

gpp relaxation

SDP 緩和のひとつにグラフ分割の問題がある。
SDPLIB にもグラフ分割の問題がいくつか含まれている。(gpp???.dat-sというもの)
グラフ分割から生成される SDP には、内点法から見ると大きな欠点があり、それは実行可能内点を持たないため、数値的に不安定になりやすい、ということである。

そこで、今日は実行可能内点をなくしている制約をすこし relaxation して実行可能内点を持たせてみることにした。これで、実際に SDPA-GMP でもきちんと解けている。
そこで、実行可能内点を数式で簡単に表現できるか?と思ってトライしてみたが、これが意外とストレートでないことがわかった。
これについては、もう少し調べてみようと思う。

今日の作業内容:gpp relaxation
今日のランチ:つかさ サーモンハラス焼き
明日の予測作業時間:4h

2010年12月13日月曜日

MFPR と machine epsilon

mpackを使っての SDP を生成するプログラムを作成。
ただ、途中でMFPRの動きがすこし怪しい感じがある。

たとえば、1+e > 1 となる最小の e を求めると prec = 600 のときに 1.0e-200 程度であり、これが実質的な machine epsilon に相当するはずだが、mpfr_printf で表示させると 600 桁に近い情報を持っていることが表示される(足し算は600桁近い情報で行っている)。
つまり、四則演算に使っている桁数と比較演算に使っている桁数にずれがあるようなのである。
いずれにしても、SDP の生成の場合は、それを見越して prec を設定する。

SDPA-GMP で解くときを考えると、SDPA-GMP のパラメータを epsilon = 1.0e-20 とするなら、その約 30 倍の prec = 600 程度であれば桁数にゆとりを持って生成できる。epsilon = 1.0e-80 なら prec = 2400 である。もちろん、SDPA-GMP の パラメータの precision も調整しておく必要がある。 epsilon の6倍程度の桁数が必要である。epsilon = 1.0e-20 なら、precision = 120, epsilon = 1.0e-80 なら precision = 480 である。

SDPA-GMP の場合、出力ファイルに relative eps の行で machine epsilon を表示してくれるので、これの桁数が epsilon の桁数の倍以上の精度になるように precision を設定する必要がある。


今日の作業内容:MFPR, センサネットワーク
今日のランチ: らく チキンカツ
明日の予測作業時間:5h

2010年12月10日金曜日

MPFR と mpreal に苦戦

昨日に続いて MPFR でプログラムを組んでいるが、これの拡張版の mpreal クラスが扱うのがなかなかに難しい。
簡単にいうと、
printf("a = %d\n", a);
b = a;
printf("b = %d\n", b);
のようなことをすると、aとbで違った表示がされる。
MPFR が原因なのか、あるいは mpreal なのか解からないが、不思議な現象である。
このとき、a の桁数が打ち切られて b に入っているようでもあり、よく解からない。
とりあえずは、あとで valgrind をかけてメモリチェックをかけて、それから詳細を確認しようと思う。

それにしても、Matlab で10秒でかけるコードを mpack で実装しようとすると5分はかかる。
mpack はマニュアルが未整備なので、関数を使うときにはソースコードを直接参照してから利用している。mpreal なども確認するためにソースコードの動きをざっと確認したりしており、これが結構時間がかかっている。

まだまだだいぶかかりそうだ。

今日の作業内容:MPFR プログラミング
今日のランチ:さか本 野菜天丼とおそばセット
明日の予測作業時間:4h

2010年12月9日木曜日

MPFR の sqrt

SDPA の関係で多倍長計算の MPFR を調べているが、sqrt の挙動でよくわからない点がある。

例えば、
  mpfr_set_default_prec(prec);
  mpf_class mtmp2 = 2.0;
  mtmp2 = sqrt(mtmp2);
  gmp_printf("sqrt(2)   in mpfr  %.80Fe\n",mtmp2.get_mpf_t());
  mpf_class residual = mtmp2 * mtmp2 - 2.0;
  gmp_printf("residual  in mpfr  %.80Fe\n",residual.get_mpf_t());
とした場合、ビット数 (prec) = 300 で
prec = 300
sqrt(2)   in mpfr  1.41421356237309504876000000000000000000000000000000000000000000000000000000000000e+00
residual  in mpfr  -1.07199229837017405496000000000000000000000000000000000000000000000000000000000000e-19
となるが 2000 にあげても
prec = 2000
sqrt(2)   in mpfr  1.41421356237309504876000000000000000000000000000000000000000000000000000000000000e+00
residual  in mpfr  -1.07199229837017405496000000000000000000000000000000000000000000000000000000000000e-19
と同じ結果が出てきている。
sqrt(2) の表示自体は桁数の表示の仕方に問題があるのかもしれないが、residual が変わらないのはおかしいような気がする。

これについては、明日続けて調べる必要がありそうだ。

今日の作業内容:MPFR チェック
今日のランチ:味庵 豚肉のキムチ炒め
明日の予測作業時間:5h

2010年12月8日水曜日

mpack のコンパイル

SDP の精度の計算用の問題を生成するのに、やはり精度の高い問題が必要と判断して、mpack を利用することにした。
ただ、かなりのコンパイル時間がかかるようで、Core2 でも5時間以上かかるようだ。
これについては、明日またチェックをする。

あと、昨日あったSDPAの細かいバグ(?)は、今日取ってもらった。
次のバージョンアップのときに公開しているソースに反映される。

SwissRoll のは久しぶりに計算をしてみたが、ある意味で致命的なミスに気がつく。
これは修正は難しいかも知れない。

今日の作業内容:mpack コンパイル
今日のランチ: 鶏こまち 鶏そぼろの蒸篭蒸し
明日の予測作業時間:3h

2010年12月7日火曜日

SDPAのデバッグ(途中まで)

SDPA はステップ長を計算するのに Lanczos 法を用いるが、どうやらここのルーチンにバグが含まれているようだ。
特定の問題、特定のパラメータで実行しないと遭遇できないバグなので見落とされていたが(99%以上のSDPには関係ないと考えられる)、なぜかステップ長を本来の値よりも大きく計算してしまう。
これについては、もう少し調べる必要がある。

今日の作業内容:センサーネットワーク下調べ, SDPA デバッグ
今日のランチ:シッダルータ 大根とジャガイモのカレー
明日の予測作業時間:6h

2010年12月6日月曜日

pthread-win32, lapack on mingw32

Debian 上の Mingw を用いてコンパイルする必要がやはりあったので、まとめてできるようにシェルスクリプトにした。
以下のスクリプトを実行すると、pthread-current, lapack-current に mingw のコンパイルのものができる。
ただし、前もって mingw をインストールしておくこと。
$ sudo aptitude -y install gcc-mingw32 mingw-w64 mingw32-binutils mingw32-runtime
あと、現状では amd64-mingw32msvc を用いてのコンパイルはできないようである。

===以下がスクリプト===
#!/bin/sh

# choose one depending on the target system
CROSS=i586-mingw32msvc-
# CROSS=amd64-mingw32msvc-

###### pthread-mingw32
echo "*******Password is anoncvs******"
rm -rf pthreads-current
cvs -d :pserver:anoncvs@sourceware.org:/cvs/pthreads-win32 login
cvs -d :pserver:anoncvs@sourceware.org:/cvs/pthreads-win32 checkout pthreads
if [ ! -d pthreads ]
then
    echo "Cannot download pthread-win32"
    exit
fi
mv pthreads pthreads-current
cd pthreads-current
make -f GNUmakefile CROSS=${CROSS} clean GC-static
cd ..

###### lapack-mingw32
rm -f lapack.tgz*
wget http://www.netlib.org/lapack/lapack.tgz
rm -rf lapack-current
tar xzf lapack.tgz
mv lapack-3.* lapack-current
if [ ! -d lapack-current ]
then
    echo "Cannot download lapack"
    exit
fi
cd lapack-current
cp INSTALL/make.inc.gfortran make.inc
sed -i.bak 's+\./test+wine ./test+g' Makefile
make \
   FORTRAN=${CROSS}gfortran \
   LOADER=${CROSS}gfortran \
   ARCH=${CROSS}ar \
   RANLIB=${CROSS}ranlib \
   blaslib lapacklib
cd .. 
 
== 以上がスクリプト ==
 
今日の作業内容:出張片付け、mingw32 チェック
今日のランチ:らく ネギとろ丼
明日の予測作業時間:6h

2010年12月5日日曜日

ZIB訪問記[7分の7]

途中で何度か目を覚ましながらも寝続けていると、機内が明るくなったことに気がついた。およそ2時間で着陸、というところまで来たようだ。朝食はソーセージとスクランブルエッグである。あまりうまく眠れなかった分、食欲がいまひとつだったが、これはボリュームが軽めだったので良かった。

最後にテレビ番組を見ることにした。BBC の番組のひとつらしく、シドニーから東京へとバイクなどで移動する、というものであった。英語だけなのでいまひとつ解かりにくいところがあったが、映像だけでも楽しめた。フライトの関係で、パプアニューギニアまでしか見ることができなかったのが残念である。

成田には9時20分ごろに着陸し、ターミナルへ。ヒースローでの待ち合わせが長かったからか、荷物が飛行機の奥のほうに入ったらしく、荷物をピックアップするのに時間がかかったが、大きなトラブルもなく成田を出て、家に帰ってきた。

家に着くと13時が目の前だったので、荷物を入れてすぐに駅前のドトールに引き返し、そこでお昼にした。ミラノサンドBとアイス抹茶ラテである。ベルリンと比べると日本は暖かいので、アイスの飲み物がピッタリであった。


今回の ZIB 訪問では、ワークショップができたこともよかったが、いろいろと研究打ち合わせを通して多くの若い研究者を知ることができたのが最大の収穫であった。
今回の打ち合わせで見えてきた方向性について、進めてみたいと考えている。

あと、ベルリンの寒さも強烈であったが、それ以上にベルリンの人たちのおもてなしの素晴らしさが印象的であった。

以上で ZIB 訪問のメモは終了である。

2010年12月4日土曜日

ZIB訪問記[7分の6]

ワークショップや研究打ち合わせなどで充実した滞在もあっという間に終わり、日本への帰国である。
朝4時30分にホテルを出て、タクシーで空港へ。Zoo の駅からテーゲル空港までは X9 のバスでも移動できるし、朝4時代なら20分おきの運行であるが、雪があってスーツケースが大変なのでタクシーを利用した。5時には空港に着いたが、British Air のカウンターが開いたのは5時40分ごろであった。チェックインして中に入ると、すぐに出国手続き、その2m隣にセキュリティチェックがある、というコンパクト設計である。
飛行機はだいたい定時に出発。早めのチェックインのおかげで、通路側の席を確保できた。
途中で機内食が出てきたが、これが驚くほど冷たいサンドイッチであった。暖かい紅茶がすごくうれしかった。

まったく来る予定のなかったヒースロー空港での待ち合わせ時間は4時間。ただ、ここでもセキュリティパスがあったので、1時間ではすこし足りないかもしれない。あと、ここの空港は1時間前にならないと搭乗ゲートがわからない、という仕組みなので、とりあえずブラブラと買い物をする。


ここではお土産を買ったが、他にも空港のわりに本が充実していた、ドイツ語の本は読めないが英語の本なら時間はかかるけどある程度読めるので、試しに2冊買ってみる。買ったのは、

Matched [Ally Condie]
http://www.amazon.co.jp/Matched-Ally-Condie/dp/0141333057/ref=sr_1_3?ie=UTF8&s=english-books&qid=1291557525&sr=1-3
What they teach you at Harvard Business School [Philip Delves Broughton]
http://www.amazon.co.jp/What-Teach-Harvard-Business-School/dp/0141037865/ref=sr_1_2?ie=UTF8&s=english-books&qid=1291556139&sr=1-2

である。1冊目はフィクションで、2冊目はビジネス書。英語としてはビジネス書のほうが簡単なので、2冊目のほうが簡単に読めると思う。
結局、なんだかんだでベルリン以上にお土産を買い込み、お土産を渡すとロンドンを目的に行ったかのように勘違いされそうだ。

フライトの1時間ちょっと前にゲート番号が表示されて、ゲートからバスで移動して飛行機へ。
飛行機では、映画などが見られない、というシステムトラブルが自分の席や近くの席で多発したが夕飯を食べ終わる頃にはこれも治った。

夕飯はテリヤキ丼をチョイス。これはこれで機内食としては悪くないけど、ベルリンでのホームパーティからはどうしても見劣りしてしまうのが残念である。ただ、United などのアメリカの飛行機に比べればかなり美味しい部類である。

帰りの映画は、もうちょっと英語の勉強、ということで「Eat, Pray, Love」にしてみた(英語の字幕つき)。日本では「食べて、祈って、恋をして」ってタイトルだったかと記憶している。
主人公の女性が離婚を経験して、イタリア、インド、バリでそれぞれ異なったタイプの男性に会い、最後のバリの男性が理想の男性である、というストーリである。
なぜ、「最後に登場する男性が理想の男性」とあらすじでネタバレしているのか気になっていたのだが、この映画は見ているとたしかに話がズルズルとしていて、かなりだるいのである。最後に一番いいものがある、とないと飽きてしまうのである。
この主人公、実は気持ちの持ちようだけで誰と結婚してもそこそこ幸せになれるし、逆に最後に再婚した相手と本当に幸せになれるか解からない。
行きの飛行機もそうであるが、帰りの飛行機もいまいちの映画に当たってしまったのは残念であった。

2010年12月3日金曜日

ZIB訪問記[7分の5]

フィンエア航空のストライキでキャンセルされてしまった帰りの便をどうするかを朝ご飯を兼ねて日本人グループで相談。
夜のうちはベルリン-ヘルシンキがキャンセルされていたが、朝になってみるとヘルシンキ-成田もキャンセルされていた。
しかたなく、朝の予定を大幅に変更してフィンエア航空に電話をすることに。
結局、フィンランドのフィンエアに国際電話をかけて、ブリティッシュエアに変更することになった。
もともとベルリンを12/4の11時50分に出発する予定が7時5分のヒースロー空港に行くことになってしまったので、明日は朝早く起きる必要が出てきてしまった。

この日は午前中をホテルで過ごしてしまったが、午後になって移動開始である。今日は夕方まで用事が入っていない日だったので、お土産を買うことにする。
まずはドイツのデパートでも最大規模、というKaDeWa に歩いて移動。入ってみてすぐに、ここは高級すぎることが判明。10分程度で退却。

もうすこし一般的なデパートということで、KaDeWa の前の駅からU2 に乗ってアレキサンダープラッツへと移動。ここにはガレリアというデパートがあり、こっちのほうが庶民的である。入り口にクリスマスツリーがあって、子供たちのいろいろとほしいものが書かれていたが、その中に「Nintendo DS」もあった。
フロアはクリスマスの色合いがやはり強く、人もたくさんであふれていた。
おもちゃ売り場には、ドイツらしく、ボードゲームが各種揃えられていた。一つほしかったが、どれも読めなかったので断念した。

 PC売り場には、ドーンとVAIO が売られていた。さすがは「世界のSONY」である。
 お土産については、いろいろと見て回ったが、1階のフロアにあったクリスマス用のチョコレートとすることにした。
ガレリアを出て、すぐにあるパークインホテルの入り口の近くにあったレストランで遅めのお昼にする。(この時点ですでに2時30分。)
メニューには英語もあったが、はっきりとイメージするのは難しい料理ばかりだった。今回は「Coffee House Symphony」というものにしてみた。noodle がドイツのものらしい、ということでこれにしてみた。
野菜が中心となっているだけあって、軽めの味であった。麺はなんか水団に近いような印象であった。ちょっとボリュームに欠けるが、ドイツに来てからカツレツだったり懇親会だったりホームパーティだったりでボリュームが多すぎたので、これくらいでちょうど良かった。


U2 を使って KaDeWa のところまで戻り、そこから歩いてホテルへ。だいたいの土地勘も出てきて方向感覚がわかってきた。
ホテルに戻ってインターネットをチェックすると、フィンエアから新しいe-チケットが送られてきていた。

このあと U3 を使って ZIB へ。研究の打ち合わせなどと並行して、今まで使わせてもらっていた部屋を片付ける。
7時15分ごろに ZIB を出発して、25分の101のバスに乗る予定だったが、どうやらバスが1本キャンセルされてしまったようで、45分のバスに乗って移動する。ベルリンは比較的電車などがきちんと動いていたので、少し驚いた。

この日は昨日とは別の研究員の自宅でホームパーティ。
ここまでもてなされるとは、日本を出発するときには思っていなかった。
最初はスープでポテトのスープ。
メインはソーセージで、このソーセージが美味しかった。
デザートはチョコクリームケーキだった。
ただ、メインの料理だけでなく、きゅうりの漬物が数種類出てきて、これが酸味があるおかげでメインのソーセージをさっぱりと食べれたのがとても良かった。
あと、ワインにいろんな香辛料などを入れて沸かして飲む、というグリューワインまで用意してくれてあった。これはかなり香りがあったようで、少し酔ってしまったかのようだった。

料理のあとにはドイツ人らしくゲームを持ち出してくれた。日本人でも解かるような簡単なものがメインであったが、これはこれで楽しかった。

帰りは U3 の駅まで歩いて、そこから地下鉄に乗ってホテルに到着。この時点で12時近くになり、飛行機の時間を考えると3時間の睡眠となることがわかった。

2010年12月2日木曜日

ZIB訪問記[7分の4]


昨日は残っていたカツレツを朝食に当てたが、この日はまたカフェに行って朝ごはんである。トマトのパイ(1.6ユーロ)とミルクティ(1.5ユーロ)である。やはり、パイはオーブンで暖ため直してくれるのがうれしい。
 昨日の夜から続いた雪のおかげで、ホテルからの景色も一面雪化粧である。

今日は午後に SCIP についての打ち合わせがあるが、午前中は時間があるので、 ZIB の人がベルリンを案内してくれることになった。
ただ、やはり雪は寒いので、まずは C&A というデパート(あるいはデパートの中にあるショップ名?)で帽子を購入。いろいろと帽子があったが2色まで絞り込んだところでどちらがいいかで迷った。ここでドイツ人らしいおばさんが近くにいたので、どっちの色が似合うかを聞いて、そちらの色をチョイス。帽子はだいたい6ユーロから10ユーロ程度。これによって、耳の痛さが取れる。

まずは、バスに乗るのだが、ホテルのあたりからだとバス停が集中しているのはベルリンの Zoo 駅の辺りである。Zoo 駅は S バーンも U バーンもあり、ベルリンの交通の要点の一つである。
(ベルリンは核となる地域が複数あり、中心がどこなのかいいづらい。東京でも渋谷、新宿、池袋などがあるのと同じである)

Zoo 駅前のバス停から乗るかと思ったが、そこを通り過ぎ、Sバーンの駅の北側に回りこむ。すると、そこにもバス停がある。Zoo 駅前から本来は発車(Zoo 駅前のバス停が1番のバス停)だが、ここでも乗れる、つまり0番のバス停、ということらしい。
今回乗る 100 番のルートは観光に適したルートだけあって乗客がとても多いが、この0番のバス停から乗ると空いているので、2階建てバスの最前列というベストポジションを確保できる。
100番ルートは乗っているだけでも観光名所を見て廻れるルートである。

 まずはシーゲスゾイレ。ドイツが昔勝った3つの戦争を記念した塔、とのことである。この次ぐらいに大統領官邸が見えてくる。ドイツは大統領が政治のトップと形式的にはなっているが、実際の権力は首相が持っているので、大統領官邸はちょっとつつましい印象である。
 バスは、連邦会議議事堂(日本でいう国会議事堂)の前を通って、ブランデンブルク門を横に小さく見て、フンボルト大学の前を通過し、世界遺産でもある博物館の島を通って、アレキサンダープラッツの駅へとつながる。
今回は、アレキサンダープラッツの少し前、マリエン教会で降りて、ここから雪の中を歩く。
マリエン教会も古い教会であるが、その前にはクリスマスのマーケットができていて、屋台が並んでいる。
 ちなみに、ここまでくればテレビ塔は徒歩圏内であるが、雪では景色を楽しめないため上らなかった。
 クリスマスマーケットにはたくさんの屋台があって、料理だったり小物だったり、見ているとついつい時間がかかってしまうので危険でもある。
 とは言っても小腹がすいた、ということで一つ食べることになった。パンにベーコンとチーズが挟まっていてパニーニに近い感じだった。周りが雪だけあって、暖かいものはとても美味しかった。
 バスの道を少し戻って博物館の島へ。ベルリン大聖堂はプロテスタントの教会ということであったが、大聖堂というだけあって大きいのが印象に残った。
 次はペルガモン博物館。博物館の島でも大きい博物館である。中にはペルガモン大祭壇が再現されており、これがものすごく大きい。ここの博物館ではオーディオガイドがあるが、日本語も含まれており、入場料を払えばオーディオガイドは別途料金がかからない。日本があるからなのか、この中で日本人グループを見かけた。

 ちなみに、イシュタールの門、という古代バビロンの門もあるが、これも大きい。どうやら大きいものをそのまま再現するのが大好きな博物館なようである。この門は第2次世界大戦のときにあまりの大きさに動かすことができずに、まわりに補強などを施したそうである。左側の一部に爆撃を受けており、それが現在にも残っている。

ペルガモン博物館だけを見るわけにも行かないので、1時間弱であとにして、フリードリヒシュトラーセ駅まであるいて、S バーンで一駅 Brandenburger Tor に着く。駅から出ると、そこはもうすぐにブランデンブルク門。ドイツの象徴のひとつでもある。目の前にクリスマスツリーがドーンとあり、左右にアメリカ大使館とフランス大使館がある。ちなみに、現在の2つの大使館は東ベルリンの位置にある。
ブランデンブルク門のすぐに裏手は東西ベルリンを隔てていたベルリンの壁が建っていたところである。今では一般の車がガンガン通行しており、道路にある2本のラインがベルリンの壁の位置を示しているだけとなっている。
ブランデンブルク門の左手、少し行くと、ユダヤ人犠牲者の記念館がある。黒い箱がいくつも並んでおり、その間を歩くことができるが、ちょっと不思議な気分でもある。長崎の原爆祈念館に行ったときと似たような感覚かもしれない。

ここからさらに少し歩くとポツダム広場がある。ここは統一後の再開発がすでにいきわたっていて、洗練された街並みの印象がある。

ここにはベルリンの壁が一部残されており、触ることさえできる。
ポツダム広場から少し歩くと、ソニーセンターがある。ソニーセンターの中はクリスマスツリーが飾られている。なお、天井の傘は富士山をイメージしたもの、ということであった。
BrandenBurger Tor から U2 で2駅、Stadmitte で U6 に乗り換えて一駅。Kochstr で降りると、そこは東西ベルリンの検問所のひとつであったチェックポイントチャーリーである。この近くには壁博物館があり、そのすこし先に展示でベルリン分割や西ベルリン包囲、ポーランドから始まるドイツ統一への流れなどが示されており、ドイツの近代史を少し勉強できる。

Kochstr で U6 に乗りなおして、2駅南下すると Mehringdamm 駅である。ここで降りてすぐに Curry36 というカリーブルストを売っているお店がある。
カリーブルストはソーセージにカレー粉とケチャップをブレンドしたものをかけて食べるもので、基本的にはスタンドみたいなところで立ち食いである。ここのお店の場合は、ポテトチップもついていてお得である。これでわずか 1.5 ユーロである。日本にもできてほしいものである。

研究打ち合わせが近づいてきたので、MehringdammからU7に乗って Mocken-brucke でU1に乗り換え、さらにWittenberg-patz で U3 に乗り換えて ZIB へと移動。

午後は SCIP での実装方法についてのレクチャーをしてもらい、そのあとでどういった共同研究ができるかを打ち合わせ。
いくつかの方向性を打ち合わせた。

この日は8時から案内をしてくれた研究員の家に招待されてのホームパーティだった。
ドイツのアパートはドイツ人らしく堅牢であったが、中は非常に広くて、何部屋も中にあった。時期が時期だけにクリスマスツリーなども飾られていた。
料理もおいしくて、まずはドイツのスープであるレンズマメを用いたリンゼンズッペ。
メインは大きなハムをまるまる焼いて、それを切り分けてであった。
デザートもチョコケーキで、これも美味しかった。
ドイツ人のホームパーティのすごさを実感してしまった夕食であった。

あと、この日の夕方にフィンエア航空がストライキに入ったことが判明。
帰りの便がキャンセルされてしまう可能性が出てきていたが、ホームパーティから帰ってフィンエア航空のページを確認してみると実際にキャンセルされてしまった。
とりあえず、12時を回っていたので日本に「帰国が1日遅れる可能性あり」というメールだけは先にしておいて寝ることにした。


2010年12月1日水曜日

ZIB訪問記[7分の3]

今日は、朝の10時から、午後5時ごろまでワークショップである。
今回の出張のメインイベントではあるが、長丁場であった。
午前中に並列計算などの話があったりなどで、充実した内容であった。

お昼は学食の2階、ちょっとしゃれたレストランである。ここではリングイネを食べてみた。他にもメニューはあったのだが、ドイツ語でいまひとつ読めないので、確実に解かっているリングイネをチョイスしてみた。味はそれなりに洗練されていてよかったが、東京でも高めのレストランに行けば食べることができる味でもある。
午後には、ZIB にあるスパコンを見せてもらうツアーがワークショップに組み込まれていた。写真が少しボケてしまっているが、参考になるかもしれないので載せておく。まずは Cray X。これは現在は使用されていないが、昔どのような計算機を使っていたかを記録しておくために普通のフロアのオブジェとしておいてある。

次が現在の主力スパコン HLRN2 である。どこもそうであるが、ファンの音と生ぬるい風がそこにはある。
スペックは http://www.top500.org/site/systems/2144に掲載されているが、http://www.top500.org/site/history/2144を見ると現在世界 64 位のスパコンである。

なお、スパコンの計算ノードも地下にあるが、データストレージはさらに下の防火倉庫に置いてある。計算ノード自体はお金次第で作り直すことができるが、データは作り直せないことがあるので、それだけ重要ということである。なお、データはテープでバックアップを取っているらしい。HDDなどもあるが、バックアップはテープが最適、ということであった。

この日の午後に自分の発表も終了。とりあえず、大きな荷物を一つ下ろすことができてホッとする。
夕飯は、U9 の終点Rathus Steglitz の近くのレストラン(名前を控えるのを忘れてしまった)で懇親会。
オードブルの時点で料理が既に期待できてしまう。
メインもいろいろとあるが、グース(鴨)かディア(鹿)が時期としておススメということだったので、グースを選択。日本ではあまりグースは食べないが、ここのグースはとても美味しかった。あと、やはりキャベツが美味しい。緑だけでなく、淡い赤っぽいのもあって、こちらも美味しい。

懇親会のあとは、U9 に乗ってホテルに戻った。


2010年11月30日火曜日

ZIB訪問記[7分の2]

この日から、本格的に活動である。
まずは、朝ごはんであるが、これはホテルからすぐ近くのカフェで取った。Steigenberger Berlin の正面を出て右に進み、最初の角で右に曲がると30mほどでカフェがある。ホテルへの近さから、圧倒的に便利である。おばちゃんが一人でまかなっているので、こぢんまりとしているが、そこがいい。
ほうれん草のパイが1.6ユーロ、ミルクティが1.5ユーロ、とお値段も手ごろである。(ホテルで朝食は取らなかったが、値段は23ユーロと書いてあった。)


この写真はサンドイッチ2.3ユーロとホットチョコレート1.7ユーロである。

そのあと、ZIB に移動するため地下鉄を利用する。Steingeberger Berlin は地下鉄の駅が2つ近いところにあり、3路線を利用できるが、ZIB に移動するには U3 の路線である。ここでは Augsburg で U3 に乗る。今回は日数がそれなりにあるので、7日間自由に乗り降りできるチケットを購入する。地下鉄などは中心街が A ゾーン、近郊が B ゾーン、そのまわりが C ゾーンとなっており、観光のメインは A,B ゾーン、ZIB も B ゾーンにあるので、A,B ゾーン共通のチケットを購入した。これが 26.20 ユーロである。1回で2ユーロ近いので、13回乗れば確実に元が取れる計算である。買ったらすぐにスタンプを機械で押して有効にする。

なお、チケット販売機はお札の認識があまく、下手に入れると認識しない。どうやら、お札の表側を上向きにして、挿入口の中央ではなく左側に沿うように入れると認識率が高いようだ。

地下鉄では、ドアは自動では開かないので、緑のボタン、あるいはレバーを引いて開けることになる。

ZIB は Dalem-Dorf でU3を降りる。駅数にして8個である。駅から ZIB までは10分。まだ寒さに慣れていない分、耳がかなり痛む。ZIB に入ってしまえば、暖房が効いていて快適である。
 写真のうち、右側と奥の建物が ZIB の建物である。左側はフリー大学という大学の建物である。一見すると ZIB が大学の組織の一つのような立地条件であるが、組織としては完全に独立しているとのことであった。


ZIB では、一緒に行ったグループでひとつ部屋を借りることができるように手配してくれてあったので、そこに荷物を置く。ここで ZIB のなかでも Optimization や SCIP に関係ある人を次々に紹介してもらう。


あいさつ回りと簡単なスケジュールを決めたところで、すぐにお昼になってしまった。お昼はフリー大学の学食で食べた。学食はいくつかあるそうだが、おいしいところまでは距離があるとのことで、5分程度学内を歩く。学食は自由に取ったあとにレジで精算するタイプである。とてもレパートリーが多く、見ているだけでも楽しめる。今回は、普通に野菜をできるだけ取れるようにしてみた。
午後に SCIP の人たちと打ち合わせ。お互いの自己紹介のあと、SDPA がどんなことをしているか、また SCIP ではどのようなことができるか、について色々と聞いてきた。ZIB の人の英語は聞き取りやすいが、疲れてくると英語においてかれることがあるので、少し注意が必要だった。

夕飯は、ホテルに一度戻ったあと地下鉄のU9で移動して Birkenstr 駅から出て1分のArema に連れて行ってもらう。ここはカツレツが有名ということで、早速それを注文。

これは、かなり美味しいカツレツだった。衣にも味がすでについているのが良かった。
ただし、ボリュームがすごい。日本でいうカツレツの2倍程度は軽くある。
下にポテトサラダが敷かれており、味は抜群であるが、これもボリュームがある。
なお、ポテトサラダの代わりにフライドポテトもあるが、それはさらにボリュームがある。
値段は、下がポテトサラダのときに10ユーロぐらい、フライドポテトで12ユーロぐらい、だったかと記憶している。
もちろん食べきれるわけでもなく、4分の1程度をテイクアウトで持ち帰る。


2010年11月29日月曜日

ZIB訪問記[7分の1]

今回は、ドイツにある ZIB (Zuse Institute Berlin) を訪問してきたので、その記録をしておく。
今回の主な目的は、研究所でのワークショップで発表することと、研究内容などを打ち合わせてくることである。

今回のフライトは、フィンエア航空のヘルシンキ経由であるため、12時ごろに成田を出発である。これに間に合わせるために、朝5時に起きて7時半ごろには家を出発。無事に成田について、フィンエアで成田第2ターミナルを出発する。
このときにユーロに両替をしたが、成田第2ターミナルでも電車を降りてすぐのところと出発ロビーにいくつか両替があり、これらは同じレートではなかった。比較してみると、1ユーロでも1円程度の差があるため、大きな金額を両替する人は一通りまわってみるとよい。(自分にはあまり関係ないが)

飛行機はかなり空いている感じであった。夕飯は匂いにつられてカレーを選択。朝はサンドイッチであった。カレーは、それなりに美味しかったのでよかった。サンドイッチはボリュームが少なめであるが、そもそも機内では運動できないので、むしろ少なめでよかった。

飛行機の中では、英語の勉強を兼ねて「ウェイトレス」という映画を観る。音声は英語、字幕は中国語で見て、日本語無しでの勉強にする。

なお、「ウェイトレス」のあらすじは、ダメな夫に愛想をつかしたウェイトレスがお金を貯めて夫から逃げようとするが、突然の妊娠で状況が一変してしまう。しかしながら、産婦人科医と不倫をはじめてしまう、という、あまり面白くないストーリであった。おそらく、純小説に似た部類なのであろう。英語の勉強にはなったが、いまひとつであった。

ヘルシンキの乗り換えは2時間程度。ヘルシンキまでの飛行機でエビアンが配られていたので、それを持ってきたのだが、ここでセキュリティチェックがあることが解かり、エビアンを一滴も飲まずに断念する。EUへの入国のパスポートチェックもあったが、今回は質問無しで簡単に入れた。

ヘルシンキからベルリンまでは約2時間のフライト。ここでも機内食がでる。パンとポテトサラダ、そしてチキンのから揚げのようなもの。冷たいのが難点であるがポテトサラダは美味しい。

ベルリンの空港にほぼ定刻に到着する。ZIB の人が空港にお迎えにきてくれるという歓迎ぶりをありがたく思いつつ、車に乗せてもらってホテルへと移動する。

今回のホテルは Steingeberger Berlin である。expedia 経由で予約をしたので、かなり予算を抑えられたが、立地条件、内装については値段以上の価値があるホテルである。ただし、メインストリートから一本入るため、夜6時以降はホテルの周りはかなり暗くなり、一人で歩くときなどは気をつける必要がある。また、このホテルは、値段の中にすでにインターネットも含まれており、ワイアレスで接続できる。ワイアレスで接続するには、ロビーで一人ずつパスワードをもらう必要がある。

ホテルについて早速メインストリートに出ると、すでにクリスマスのイルミネーションが飾られており、クリスマスマーケットが出ている。

ここでベルリン最初の夕飯を食べた。


ここは屋台なので外で食べることになり相当に寒かったが、これは結構美味しかった。特にキャベツはこの季節限定のものということで、日本のキャベツとは異なり、甘みが強くて良い。

いずれにしても、相当な寒さであり、ヨーロッパセンターなどを少し見た程度でホテルに戻る。厚着が必要だということを実感する。
(東京とは15度ぐらいの温度差があり、12月上旬で東京の一番寒い季節と同じかそれよりも寒くなる)

2010年11月26日金曜日

多様体

今日は、すこし雰囲気を変えるために別の勉強をいれた。
いろいろと勉強になるが、特に勉強になったのが
「n次元リーマン多様体は n(n+1)/2 次元の任意の実解析的リーマン多様体に等長埋込可能である。」
というところである。
これはなんか関係がありそうである。

今日の作業内容:多様体
今日のランチ:つかさ ブリの照り焼き

2010年11月25日木曜日

Ubuntu の ATLAS は 10.10 からディレクトリが変更されている

今日インターネット上で少し調べてみたところ、Ubuntu で SDPA のコンパイルがうまく行かないときがあるようである。
原因を調べてみると、ATLAS のインストールされるディレクトリが 10.10 (Marverick) から変更されて、Debian と同じところになっているようである。
つまり、/usr/lib/atlas-base/libblas.a が /usr/lib/atlas-base/atlas/libblas.a に変更されている。
とりあえず、この違いを吸収できるように configure などのスクリプトを修正しておいた。

あと、今日の午後は、いまひとつ作業の調子が出ず。
少し疲れがあるのかもしれない。

今日の作業内容:Ubuntu 対応
今日のランチ:日高屋 レバニラ炒め
明日の予測作業時間:4h

2010年11月24日水曜日

出張準備とSDPAのconfigure調整

ドイツ出張が迫ってきたので、出張準備をしておいた。
飛行機やホテルなどの必要な情報をプリントアウトして、整理しておいてある。

また、SDPA の configure.in についても、さらに改良した。
SDPA-M については、追加でいろいろとコマンドができているので、こちらについても CommandList.txt というファイルで説明を書くことにした。
これらのコマンドを使うと、
(1) SDPA フォーマットへの書き出し
(2) SDPA,SDPARA の結果ファイルの読み込み
などが行える。とくに (2) を使うと、SDPA Online solver の出力ファイルを Matlab に読み込み直せるので、実はかなり便利である。

今日の作業内容:出張準備, configure 調整
今日のランチ: たちばな いわしのお寿司
明日の予測作業時間:4h

2010年11月23日火曜日

最短路の部分、mex 化

センサーネットワークのプログラムの一部にあった最短路だが、ボトルネックになっていたのでやはり mex にした。
もともと、スタート地点が一つでないため、Floyd–Warshall algorithm をベースにしていたが、アルゴリズムを整理したうえで mex にしたおかげで 30 倍程度の高速化になっている。
これによってボトルネックにならずに済みそうである。

ところで、最短路問題は基本的な問題であるため、非常に多くの実装があるし、ヒープなどを利用して高速化などが行なわれている。
しかし、スタート地点が複数でしかも全部の地点がスタートではない、という状況になるとあまり研究がなされていないようである。こういったときに、どれだけヒープなどで高速化できるのか、ということも良く解からないのか簡単には見つけることが難しい。

今日の作業内容:最短路 mex 化
明日の予測作業時間:5h

2010年11月22日月曜日

SDPAとMUMPS

SDPA のパッケージの中には MUMPS のパッケージがある。
しかし、Ubuntu, Debian では MUMPS のパッケージがあるので、SDPA の中のパッケージを利用する必要はない。
今まで、この違いを configure で吸収させていなかったが、修正をして既存の MUMPS パッケージがある場合にはそれを利用することにした。
これによって --with-mumps-include, --with-mumps-libs というオプションがついている。
また、Makefile.am で mumps 系のファイルをインストールしないように条件分岐も入れるようにしておいた。

今日の作業内容:MUMPS と configure
今日のBGM: FF12 OST [4]
今日のランチ:つかさ 〆さば

2010年11月19日金曜日

プロファイリング

SDPA の論文の校正をするにあたって、比較対象の SeDuMi, SDPT3, CSDP のそれぞれに計算時間を測定する修正を追加している。
これによって、SCM の計算とそのコレスキー分解の各計算時間が算出できるようになる。

数問だけ比較してみているが、同じ計算機でもコレスキー分解にかかっている時間にかなりの違いがある。反復回数で割って1回ごとの反復にしても、かなり違っているのである。今まで気がついてなかったが、面白い結果である。

今日の作業内容:センサーネットワークの問題を確認、プロファイリング準備
今日のランチ:らく しょうが焼き定食
明日の予測作業時間:5h

2010年11月18日木曜日

SDPAの configure にバグがあるようだ

今日はあまり作業の時間がとれなかったので、明日以降のメモのみ。

SDPA は 7 以降で configure でインストールできるが、この一部にバグがある、という報告をもらった。どうやら Debian の kfreebsd だと -lpthread が追加されずに停止するようである。
しかも、このバグは BLAS にリンクできるかどうかをチェックしている段階で発覚するので、BLAS のリンクに失敗しているのか pthread に失敗しているのかがわかりにくい。
pthread を確認するように AC_CHECK_FUNC を追加することとしよう。

あと、AC_CHECK_FUNC で失敗したときに、config.log の中身を表示できるととても便利なので、そういった機能があるのかも確認する必要がある。

今日の作業内容:SDPA configure の状況確認
今日のランチ:らく 麦とろろセット
明日の予測作業時間:3h

2010年11月17日水曜日

Lovasz Workshop で Lovasz と少しだけ話ができた

今日は京都賞を取った Lovasz の受賞記念ワークショップということで、話を聞きに行ってきた。
他にも作業があったのであまりたくさんは聞けなかったが、William Cook の話では TSP の話だった。TSP は有名な問題であるが、厳密解を求める理論的なオーダーは半世紀も改善されていない、という点が驚きであった。

今日の最後が Lovasz の話であり、graphon の話であった。graphon はグラフの隣接行列を拡張したようなものであって、グラフの隣接行列であれば各要素は 0 or 1 であるが、graphon の場合には 0 から 1 の値が取れるように拡張されている。
この graphon の説明や、その性質、それから導かれる内容などが話であった。

そのあとの懇親会でも Lovasz は色々な研究者と話をしていたが、タイミング的に暇になっているところがあったで「このタイミングはラッキーなのでは?」と思い、話しかけてみたところ、少しだけ話をすることができた。

どうやら、graphon の勉強を始めたのは 5,6 年前ぐらいで、行列の収束などに興味を持ったのが研究のスタート地点だったようである。
ワークショップの話では数学的な側面に話が集中していたが、このような収束はインターネットなどのネットワークの研究に役立つ、といった応用がある、とのことであった。
graphon について知りたいのであれば、
"Very Large Graph" http://arxiv.org/abs/0902.0132
がサーベイを兼ねていて取っ付きやすいかもしれない、とのことであった。
(注:英語で話している関係で、一部に間違いを含む可能性あり)


graphon は SDP と直接関係があるかどうかはわからないが、Lovasz theta は SDP においても重要な問題のひとつなので、ひょっとしたら関係があるのかもしれない。


今日の作業内容: Lovasz Workshop
今日のランチ:弁当 チキンガーリック
今日の夕飯:ワークショップ懇親会

2010年11月16日火曜日

SDPA 論文校正の打ち合わせ

今日は、SDPA の論文校正の打ち合わせをした。
大きな項目としては、数値実験の問題をどのように選択するか、ということと SDPA-GMP の数値実験をどうするか、が検討課題になりそうである。
このあたりは、まだまだ検討すべきである。

また、最短路については、splib の dikbd.c を C++ に書き直しているが、バグが混入したようでデバッグが必要となっている。これについては、明後日以降見直すことにする。

今日の作業内容:
8:15-9:15 dikbd.c 編集その1
10:30-11:00 SDPA 論文校正検討
11:00-11:30 dikbd.c の C++ 化
11:30-12:00 dikbd.cpp のデバッグその1
13:15-14:00 dikbd.cpp のデバッグその2

14:00-15:00 dikbd.cpp のデバッグその3
18:30-20:30 SDPA 校正打ち合わせ
今日のランチ:味庵 牛肉のブラックペッパー炒め
明日の予測作業時間:2h

2010年11月15日月曜日

最短路の基本的な勉強

この前教えてもらったところでは、最短路問題の基本的な勉強としては、

[教科書1] Network Flows: Theory, Algorithms, and Applications
               Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
[教科書2] Network Optimization
              Dimitri P. Bertsekas
のあたりであり、とくに[教科書1]は2章割いてあるだけあって、基本的なことについてかなり詳しい。
また、実装としては、Andrew Goldberg の Network Optimization にある
http://www.avglab.com/andrew/soft.html
の SPLIB が基本的な実装を網羅している。
この実装は、このページにもあるように Math Prog で比較実験の論文が出ているので、これも参考になる。


とりあえず、上記の情報をベースに進めているが、いろいろと問題もある。
SPLIB は実装が古いので、かなり読みにくくなっている。
特にデータ構造のあたりを無理なマクロを使用して書いているので、このあたりがきつい。
まずは、これを C++ で書き直して、どの程度の性能が出るのかを見てみたい。

あと、これもクリティカルな状況だが、今回の最短路についてはあくまで SDP 処理の前処理であるため、正確な最短路ではなく、SDPにとって都合のいい最短路がベターである。
つまり、目的関数が厳密でないため、厳密解法がいいとも限らず、頭が痛いところである。

今日の作業内容:
10:00-10:30 [ng] parser_db.c 解読
10:30-10:50 [ok] 解読続き
14:00-14:30 [ok] 枝の重さ 確認
14:30-15:30 [ng] dikbd.c 確認
15:30-16:00 [ok] STLのヒープの確認
16:00-16:30 [ng] dikbd.c 続き
16:30-17:00 [ok] dikbd.c 続き
17:00-18:00 [ok] dikbd.c を C++ に書き直し その1
今日のランチ:四川 豚の角煮弁当
明日の予測作業時間:4h

2010年11月12日金曜日

Intel MKL での SDPA,SDPARA リンク

SDPA, SDPARA のコンパイルができたので、そのメモをしておく。
基本的に Intel MKL の場合、C は icc, C++ は icpc, Fortran は ifort なので、SDPA の場合には、最終的に icpc でリンクしている。

icpc -openmp -O -funroll-all-loops -fPIC -o sdpa sdpa_exe.o -L. -lsdpa \
-L${mumps_dir}/single/lib -ldmumps -lmumps_common -lpord -L${mumps_dir}/mumps/single/libseq -lmpiseq -L/opt/intel/11.1.072/mkl/lib/em64t -lmkl_intel_lp64 -lmkl_core -lmkl_intel_thread -L/opt/apps/isv/intel/11.1.072/lib/intel64 -lifcore

のような感じでリンクしている。
なお、MUMPS については、Makefile.INTEL.SEQ を Makefile.inc にしているが、CC が gcc になっているので、これを CC = icc に修正している。

SDPARA の場合の最終リンクは
mpicxx -O -funroll-all-loops -openmp -fPIC -o prsdpa sdpa_exe.o libprsdpa.a \
-L${mumps_dir}/parallel/lib -ldmumps -lmumps_common -lpord \
-L/opt/intel/11.1.072/mkl/lib/em64t -lmkl_scalapack_lp64 -lmkl_blacs_openmpi_lp64 -lmpi_f77 \
-L/opt/intel/11.1.072/mkl/lib/em64t -lmkl_intel_lp64 -lmkl_core -lmkl_intel_thread \
-L/opt/intel/11.1.072/lib/intel64 -lifcore
のようにしている。
これで mpirun で実行できるが、このまま単純に実行すると SDPA 自体のマルチスレッドと MKL の OpenMP が衝突するので(CPU使用率が2000%を超えたりする)、
export OMP_NUM_THREADS=1
として、OpenMP を1スレッドだけにするように設定している。

ただし、今日のところは PBS にうまく submit できていないようで、PBS からの実行はできていない。


今日の作業内容:SDPA, SDPARA コンパイル + SDPA パッケージング + 最短路問題下調べ
今日のBGM: FF12 OST [2,3,4]
今日のランチ:らく 鶏くわ焼丼とおそば
明日の予測作業時間:4h

2010年11月11日木曜日

GotoBLAS コンパイルと今から打ち合わせに

GotoBLAS については、
../kernel/x86_64/gemm_ncopy_4.S:175: Error: undefined symbol `RPREFETCHSIZE' in operation
というメッセージが出ていたが、これについては getarch.c の
#define FORCE_NEHALEM
を有効にすることで回避できた。今回のCPUは Westmere-EP のモデルのようであるが、getarch.c にWestmere-EP に相当する部分はなかったので、
http://ja.wikipedia.org/wiki/Xeon
を参考にして一番近そうな Nehalem を選択しておいた。
コンパイルには、
make BINARY=64 CC=icc FC=ifort USE_THREAD=1 USE_OPENMP=1 NUM_THREADS=24
としてある。
これで SDPARA のコンパイルに一歩前進である。

ただ、たったいま気がついたが、intel compiler といっしょに MKL が入っていた。
これを使うのもひとつの手である。

あと、昨日出したメールについて昨日の夜のうちに返信があり、飛行機の乗り継ぎの関係で今夜だけ日本に一泊するとのことで、スケジュールを変更して今日の夜に打ち合わせをすることになった。

今日の作業内容:GotoBLAS コンパイル + 打ち合わせ準備
今日のランチ:味庵 ピリ辛炒めの揚げ豆腐
明日の予測作業時間:4h

2010年11月10日水曜日

GotoBLAS2 がエラーでコンパイルできていない

SuSE11 の計算機で SDPARA をコンパイルできるかどうか試してみているが、GotoBLAS2 でコンパイルエラーになっている。
メモとして書いておくと、

../kernel/x86_64/gemm_ncopy_4.S:175: Error: undefined symbol `RPREFETCHSIZE' in operation

のようなメッセージが出る。どうやら、CPU の自動認識に失敗しているようで、RPREFETCHSIZE の #define が取り込まれていない様子である。
CPU 自体は、
$ cat /proc/cpuinfo | grep Xeon | head -1
model name : Intel(R) Xeon(R) CPU X5670 @ 2.93GHz
となっている。

これについては、明日また調べることにする。

あと、最短路の論文をチェック。
論文では数値実験をしているが、どうやらグラフの密度でだいぶ性能が左右されるようだ。
とりあえず数値実験に用いたプログラムを入手できるかどうかを著者にメールしてみた。
入手できないのであれば、自分で組むことになる。

今日の作業内容:
6:30-7:00 [ng] 文字のプログラム改良
7:00-8:00 [ok] 改良の続き
11:00-12:00 [ng] MPSP 論文チェックp1-p6
15:00-15:30 [ok] 計算機設定整理
16:45-17:30 MPSP論文チェックp5-p8
今日のBGM: FF7 OST [1,2]
今日のランチ:シッダルータ ポテトとグリーンピースのカレー
明日の予測作業時間:2h

2010年11月9日火曜日

並列計算の数値実験の論文へのまとめ方

昨日に続いて、数値実験の論文へのまとめ方についての論文を読む。今回は並列計算に関するものである。

Reporting Computational Experiments with Parallel Algorithms: Issues, Measures, and Expert's Opinions
ORSA Journal on Computing

1995年のものなので、コンピュータ名などは古い印象がある。

並列計算の指標などについてまとめられており、抜粋すると、

Speedup(p) = (特定の計算機上で最も高速なシリアル計算での計算時間)/(p台使用時の計算時間)
RelativeSpeedup(p) = (並列ソフトを1台で実行したときの計算時間)/(p台使用時の計算時間)
AbsoluteSpeedup(p) = (いろんな計算機で実行したシリアル計算の最短時間)/(p台での並列計算の計算時間)

efficiency(p) = S(p) / p
[ただし、S(p) は Speedup(p),RelativeSpeedup(p),AbsoluteSpeedup(p)]
incremental efficiency = ((p-1)*(p-1台での計算時間))/(p*p台での計算時間)

といったところである。

ただし、これらの計算も実は状況によって様々に異なることが指摘されており、どれがいいかについては疑問が残る。
この論文では、どのような指標がよいか23人の研究者からアンケートを取っているが、これがバラバラである。
要するに研究者の中でも並列計算を評価する指標はコンセンサスが取れていない。

今日の作業内容:
6:30-7:00 [ok] 数値実験の仕方の論文 並列計算について [その1]
7:00-7:30 [ok] p10-p20
8:00-8:30 [ok] p28-p34
8:15-8:45 [ok] 最短路アルゴリズム確認
10:00-11:00 [ok] アルゴリズム調査
11:00-11:30 [ok] Floyd-Warshall のアルゴリズム確認
11:30-12:00 [ok] Folyd-Warshall 関連の論文を調査
13:30-14:30 [ng] SNL サンプル作成
今日のBGM: FF12 OST [1,2]
今日のランチ:角笛 さばの竜田揚げ
明日の予測作業時間:5h

2010年11月8日月曜日

最短路問題

今日は、SDPAの論文について、レフリーから教えてもらった、数値実験の方法に関する論文に目を通した。

Designing and Reporting on Computational Experiments with Heuristic Methods
Journal of Heuristics, 1:9-32, 1995

特に重要なのはP11(論文内では3ページめ)にある Table 1 である。これがこの論文の要点である。
抜粋しておくと、
1. Define the goals of the experiment.
2. Choose measures of performance and factors to explore.
3. Design and execute the experiment.
4. Analyze the data and draw conclusions.
5. Report the experiment's results.
あと、Table 2 も有益である。
1. Reproducibility is essential.
2. Specify all influential factors in details.
3. Be precise about timing.
4. Show how algorithm parameters are set.
5. Use statistical experimental design techniques.
6. Compare the heuristic with other methods.
7. Reduce variability of results.
8. Produce a comprehensie report of the results.

これらは、今後の改訂に活かしていこう。

あと、SNL のプログラムの一部で最短路問題がボトルネックになっているので、それを解消するための改良をスタート。
Matlab のプログラムをいろいろと書き直したところ、だいたい10倍程度の高速化になった。
これを C++ で書けば、さらに2倍から5倍程度は高速化できそうな手応えはあるが、問題はそれでもボトルネックに成りかねないところである。
多点スタート多点ゴールの最短路問題で、しかも他にも条件分岐が入っているので、おそらくダイクストラ法はあまり高速化できなそうな気がする。
最短路問題のアルゴリズムはバラエティに富んでいるので、どのアルゴリズムなら効率的かを考えるところから始めたほうがよさそうである。

今日の作業内容:
6:45-7:15 [ok] SNL 論文復習
13:20-14:00 [ng] 事務処理いろいろ
14:00-14:20 [ok] 事務処理続き
14:20-14:50 [ok] データ整理
17:00-18:00 [ok] Matlab プログラム改良
18:00-18:30 [ok] 改良つづき
今日のランチ:つかさ 生サーモン照り焼き
明日の予測作業時間:4h

2010年11月5日金曜日

Wake On LAN の設定

Debian や Ubuntu は普段あまり使わないので、Vista の上の VMWare で動かしているが、Vista 自体もあまり動かしていないので、必要なときだけネットワーク経由で電源を入れられるように変更。
こういった機能は Wake On LAN と言って、オンボードの LAN 経由で起動できることが多い。

Windows Vista で Wake On LAN に対応させるときには、
http://tomorrow.meyon.gonna.jp/?eid=621382
がとても参考になる。
今回は、BIOS 画面で、[On Board LAN BOOT ROM] を [Enabled]にして再起動した。
(BIOSの項目はBIOSごとに異なるので、必ずしも同じ名前ではない)

そのあとは、[デバイスマネージャ]->[ネットワークアダプタ]->[LANにつながっているもの]->[プロパティ]->[電源の管理] と選んで[このデバイスで、コンピュータのスタンバイ状態を元に戻すことができるようにする]をチェックする。

また、このときにコマンドプロンプトから
ipconfig /all
としておいて、実際に使っている LAN カードの MAC アドレスを取得する。
具体的には、Physical Address と書いてあるところで、00-AA-BB-CC-11-22-33 と16進数で書かれている。

ここで、Windows Vista を終了する。
この Vista を今回は別サーバの RedHat からネットワーク経由で起動する。
RedHat では
# yum install wol
で wol コマンドをインストールする。
ここで
$ wol 00:AA:BB:CC:11:22:33
とすると、Vista PC が起動する。
(MAC アドレスが Windows 上だとハイフンだけど Linux 上だとコロンなところに注意)

なお、Windows Vista に外側からアクセスするには、VNC や cygwin による SSH などが必要である。VNC は UltraVNC などでできるようにあるが、dsm プラグインを設定したり、アクセスを変更したりなどが必要である。
また、cygwin の場合は、SSH をインストールしておく必要がある。これも他のサイトにいろいろと情報がある。なお、SSH でログインした場合、終了するときのコマンドは
$ shutdown.exe -s now
である。Linux なら -h であるが、-s である点に注意が必要である。
また、shutdown.exe は cygwin のコマンドであり、デフォルトでは入らないようなので、自分で入れる必要がある。shutdown.exe を実行すると、cygwin だけでなく Windows Vista 自体が終了するので、また必要なら wol で起動しなおす。

今日の作業内容:
8:30-9:00 [ok] SFSDP での実験
10:00-10:30 [ok] 事務処理関係チェック
13:00-13:30 [ok] Wake On LAN 設定
13:30-14:00 [ok] SFSDP での実験、大きめ
14:10-14:40 [ok] 発表原稿チェック
14:40-15:30 [ng] SeDuMi 中身チェック
15:50-16:30 [ok] SDPA 論文校正内容検討その1
16:30-17:00 [ng] SDPA論文校正内容検討その1まとめ
17:30-18:00 [ok] SDPA論文校正内容検討その1まとめ続き
今日のBGM: Romasing SAGA 3 OST [1-3]
今日のランチ: らく 山芋定食
明日の予測作業時間: 5h

2010年11月4日木曜日

SDPA の論文の校正スタート

1月最後に投稿していたSDPAの論文がようやくレフリーから返却されてきた。
かなり大幅な校正が必要、という判断であったが、reject されなかっただけ良かったと考えて、早速校正をするべきかと思う。
なにはともあれ、レフリーレポートを良く読んで、どのように校正すべきかを検討するところからスタートである。

あと、semidefinite embedding のは、読んだ論文の数値結果はどうやら SFSDP のよりもかなり高速である。ただ、データが特殊なので、論文で提案している手法が効果的なのか、あるいはデータの特質で高速に解けるのかを切り分ける必要がある。とりあえず、データを生成するプログラムは昨日作成したので、これを SFSDP にかけることになる。

今日の作業内容:SDPA 校正スタート、データ生成
今日のランチ:らく チキンカツ
明日の予測作業時間:5h

2010年11月1日月曜日

こまごまとした処理

今日は、こまごまとした内容を片付けただけで終了。
(したがって、細かい時間についてはメモをしていない)
基本的には、先週後半の学会出張の会計処理がメインで、あとは先週前半に作成したレフリーレポートの内容確認。
レフリーレポートはこれで完成なので、時期を待って返却すれば大丈夫である。

他に、Windows Vista を週に1度自動的に再起動するようにする設定をしておいた。

今日の作業内容:会計処理、レポート作成
今日のランチ:信華園 マーボー丼
明日の予測作業時間:6h

2010年10月27日水曜日

査読レポート作成

今日は午前中に査読レポートを作成。
査読なので、詳細はここでは省略。
レポートとして一通り書いたので、あとでもう一度見直してから提出すればOKそうだ。

今日の作業内容:
6:30-7:30 [ok] 査読論文読み込み
8:00-9:00 [ok] 査読論文プログラムチェック
10:00-11:00 [ok] 査読論分の周辺情報確認
10:30-11:30 [ok] 査読論文 Major Comment 作成
11:30-12:30 [ok] 査読論文 Minor Comment 作成
今日のBGM: DQ III,IV
今日のランチ: 食堂 ハンバーグ定食
明日の予測作業時間:2h

2010年10月26日火曜日

objdump で dll の確認 & semidefinite embedding

昨日の SDPA を mingw でコンパイルしたものであるが、mingw でコンパイルしたときにどの dll が必要となるかは Linux 同様に objdump で確認できる。
実行すると
$ i586-mingw32msvc-objdump -p sdpa.exe | grep "DLL Name"
DLL Name: KERNEL32.dll
DLL Name: msvcrt.dll
DLL Name: msvcrt.dll
となり、pthreadGC2.dll を必要としていないことが確認できる。ちなみに、pthreadGC2.dll 自身は
$ i586-mingw32msvc-objdump -p pthreadGC2.dll | grep "DLL Name"
DLL Name: KERNEL32.dll
DLL Name: msvcrt.dll
DLL Name: WSOCK32.DLL
となり、WSOCK32.DLL を必要としていることが解る。(static でリンクしたときに、libwsock32.a をリンクしていたのは、このため)


あと、semidefinite embedding については、ここ最近で以下の論文を読んでおいた。
[1] Fast Graph Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
by X. Wu, A. So, Z. Li, S.Li
[2] Embedded in the Shadow of the Separator
by F. Goring, C. Helmberg, M. Wappler
[3] Dimensionality Reduction: A comparative Review
by L. Maaten, E. Postna, J. Herik

[1] は Semidefinite Embedding が、 Markov Process の収束を最適化する問題と primal-dual になっている、という点が面白い。
[2] は、低次元に埋め込んだときに、あるカットで点を2つのセットに分割すると、どちらかのセットのすべての点は原点とその点の間にカットが挟まる、ことを言っている。ただ、証明の難しさの割には、今後の展開には使えなさそうである。
[3] は survey 論文。これまでの手法を整理し、数値実験で比較している。特に、Appendix に数値実験用の人工データをどう作るか、という式が載っており、Swiss Roll はこの式で生成できるようだ。

今日の作業内容:
6:30-7:00 [ok] Dimension Reduction Survey 読み p14-p18
7:00-7:30 [ok] Dimension Reduction Survey 読み p19-p26
7:30-8:30 [ok] 読んできた論文の整理
10:20-11:00 [ok] 査読論文読みはじめ
17:00-18:00 [ok] 査読論文続き
今日のランチ:らく 焼魚定食
明日の予測作業時間:3h

2010年10月25日月曜日

DLL なしのSDPA の Windows バイナリのコンパイル方法

昨日のコンパイル方法では、pthread が dll となってしまうため、これを static でリンクすることにした。
これによって pthreadGC2.dll を別途コピーする必要なく Windows 上で実行できるようになる。

static にするのは、pthread-win32 のページで配布されている tar.gz ではうまく行かなかったため、cvs でソースを持ってくる。参考にしたのは、
http://blog.k-tai-douga.com/article/39079027.html
であるが、つまり
$ cvs -d :pserver:anoncvs@sourceware.org:/cvs/pthreads-win32 login
で cvs のログイン情報を乗せる(パスワードは、anoncvs である。)
このあと、
$ cvs -d :pserver:anoncvs@sourceware.org:/cvs/pthreads-win32 checkout pthreads
とすると、pthread-win32 が取り出せる。
コンパイルは、
$ make -f GNUmakefile CROSS=i586-mingw32msvc- clean GC-static
である。
これにより、libpthreadGC2.a が作られる。pthreadGC2.dll があると dll が必要となるので、これが生成されていないことを確認しておきたい。

次に、SDPA 7.3.2 の configure としては、

export CFLAGS="-D__CLEANUP_C -O3 -finline-functions -DPTW32_BUILD_INLINED -DPTW32_STATIC_LIB -I(どこか)/pthreads -I. -DHAVE_CONFIG_H -Wall"
export FCFLAGS="${CFLAGS}"
export CXXFLAGS="${CFLAGS}"
./configure --prefix=(どこか)/sdpa-install --build=x86_64-unknown-linux-gnu --host=i586-mingw32msvc --target=i586-mingw32msvc --with-blas="(どこか)/lapack-3.2.2/blas_LINUX.a (どこか)/pthreads/libpthreadGC2.a /usr/i586-mingw32msvc/lib/libwsock32.a" --with-lapack=(どこか)/lapack-3.2.2/lapack_LINUX.a

ポイントは、
[1] PTW32_STATIC_LIB を define した上で pthread.h を include すること。(これをしないと __imp__pthread_??? という関数ができてしまい、リンクできなくなってしまう。)
[2] libpthreadGC2.a と一緒に libwsock32.a もリンクすること。
である。
SDPA の場合、--with-blas のところに来ているライブラリが最後の方にリンクされるので、ここに無理に追加している。

これで
$ make
とするが、もちろん、MUMPS で失敗する。
$ cd mumps/build
として、
Makefile.inc の最後に以下の2行を追加する。
AR = i586-mingw32msvc-ar vr
RANLIB = i586-mingw32msvc-ranlib
このあとで mumps/build で
$ make clean d
で mumps のライブラリはコンパイルできる。
(このとき、PTW32_STATIC_LIBが define されていることも分かる)

そのあと、sdpa-7.3.2 のディレクトリに戻って
sdpa_tool.cpp, sdpa_newton.h
に昨日と同じ修正を施して、
$ make
とすると、sdpa.exe ができる。
$ wine ./sdpa.exe example1.dat-s example1.result
で実行できるのを確認してから Windows 上にコピーする。
(もちろん、dat-s ファイルは nkf で改行コードを変更しておく。)

なお、ros_500.dat-s を解いたところ、native の SDPA と wine 上の SDPA だと 10 倍程度の計算速度の違いが出る。

最終的には出来上がったが、PTW32_STATIC_LIB に気づくまでに1時間間30分以上をロスしてしまった。

今日の作業内容:
6:30-7:30 [ok] Embedded in the shadow 読み p1-p10
7:45-8:30 [ok] 会議用投稿の査読
10:00-10:30 [ng] pthread-win32 static compile
10:30-11:00 [ng] pthread-win32 static compile
11:00-11:30 [ng] pthread-win32 static compile
13:00-14:00 [ok] SDPARA 原稿校正
13:30-14:30 [ng] pthread-win32 static compile
14:30-15:30 [ok] pthread-win32 static compile
15:30-16:00 [ok] Embedded in the shadow 読み
今日のランチ:しなの カツオのタタキ丼とうどんのセット
明日の予測作業時間:5h

2010年10月24日日曜日

SDPA の Windows バイナリのコンパイル方法

前回、一度行ったが、今日改めてやって見たところ、メモに残さないと覚えていられないほど面倒であることが分かった。

ここにメモを書いておく。

まずは、Debian or Ubuntu で Synaptic を使って
gcc-mingw32, mingw32-runtime, mingw32-binutils, wine
をインストールする。
これにより、以下のコマンドが使えるはずである。
i586-mingw32msvc-g++,i586-mingw32msvc-gfortran,i586-mingw32msvc-ar,i586-mingw32msvc-ranlib, wine

次に、lapack-3.2.2 の lapack.tgz をダウンロードしてきて、
cd lapack-3.2.2
cp INSTALL/make.inc.gfortran make.inc
でそのあと、以下の修正をする。
$ diff INSTALL/make.inc.gfortran make.inc
19c19
< FORTRAN = gfortran
> FORTRAN = i586-mingw32msvc-gfortran
23c23
< LOADER = gfortran
> LOADER = i586-mingw32msvc-gfortran
43c43
< ARCH = ar
> ARCH = i586-mingw32msvc-ar
45c45
< RANLIB = ranlib
> RANLIB = i586-mingw32msvc-ranlib
さらに、Makefile も以下のように修正する。
$ diff Makefile.org Makefile
17,18c17,18
< ( cd INSTALL; $(MAKE); ./testlsame; ./testslamch; \
< ./testdlamch; ./testsecond; ./testdsecnd; ./testversion )
---
> ( cd INSTALL; $(MAKE); wine ./testlsame; wine ./testslamch; \
> wine ./testdlamch; wine ./testsecond; wine ./testdsecnd; wine ./testversion )

これで、
make blaslib lapacklib
により、blas_LINUX.a, lapack_LINUX.a が生成される。

次に、pthread-win32 をダウンロードしてくる。
mkdir -p (どっか)/pthread-win32/include
cd (どっか)/pthread-win32/include
wget http://mirrors.kernel.org/sources.redhat.com/pthreads-win32/prebuilt-dll-2-8-0-release/include/pthread.h
wget http://mirrors.kernel.org/sources.redhat.com/pthreads-win32/prebuilt-dll-2-8-0-release/include/sched.h
wget http://mirrors.kernel.org/sources.redhat.com/pthreads-win32/prebuilt-dll-2-8-0-release/include/semaphore.h
mkdir -p (どっか)/pthread-win32/lib
cd -p (どっか)/pthread-win32/
wget http://mirrors.kernel.org/sources.redhat.com/pthreads-win32/prebuilt-dll-2-8-0-release/lib/pthreadGC2.dll
wget http://mirrors.kernel.org/sources.redhat.com/pthreads-win32/prebuilt-dll-2-8-0-release/lib/libpthreadGC2.a

次に、sdpa-7.3.2 のソースディレクトリに移動して、

./configure --prefix=${HOME}/sdpa-install --build=x86_64-unknown-linux-gnu --host=i586-mingw32msvc --target=i586-mingw32msvc --with-blas=(どっか)/blas_LINUX.a --with-lapack=(どっか)/lapack_LINUX.a

によりコンフィグを通す。
これで make をすると mumps のコンパイル中に pthread.h が見つからず止まる。

cd mumps/build で Makefile.inc に以下の修正。
$ diff Make.inc/Makefile.inc.generic.SEQ Makefile.inc
77c77
< AR = ar
> AR = i586-mingw32msvc-ar
80c80
< RANLIB = ranlib
> RANLIB = i586-mingw32msvc-ranlib
117c117
< inc = $(INCSEQ)
> INC = $(INCSEQ) -I(pthreadのディレクトリ)/include
119a120,127
> CC = i586-mingw32msvc-gcc
> FC = i586-mingw32msvc-gfortran
> FL = i586-mingw32msvc-gfortran
> OPTC = -g -O2 -O2 -funroll-all-loops
> OPTF = -g -O2 -O2 -funroll-all-loops
> OPTL = -g -O2 -O2 -funroll-all-loops
> LPORDDIR = (どっか)/sdpa-7.3.2/mumps/build/PORD/lib/
> IPORDDIR = (どっか)/sdpa-7.3.2/mumps/build/PORD/include/

これで mumps/build で
make clean; make d
を実行する。

さらに、sdpa-7.3.2のディレクトリの Makefile を以下のように修正する。
$ diff Makefile.org Makefile
104,105c104,105
< $(LDFLAGS) -o $@
< default_includes = -I.
> $(LDFLAGS) -o $@
> DEFAULT_INCLUDES = -I. -I(pthreadのどっか)/include
200c200
< FCLIBS =
> FCLIBS = -L/usr/lib/gcc/i586-mingw32msvc/4.4.4 -L/usr/lib/gcc/i586-mingw32msvc/4.4.4/../../../../i586-mingw32msvc/lib (pthreadのどっか)/lib/libpthreadGC2.a -lgfortranbegin -lgfortran -lmingw32 -lmoldname -lmingwex -lmsvcrt -luser32 -lkernel32 -ladvapi32 -lshell32

さらに sdpa_newton.h の 33 行目に
#include <pthread.h>
を追加し、sdpa_tool.cpp では、
#include <sys/times.h>をコメントにし、
double Time::rGetUseTime() 関数を削除する。

これで make すると sdpa.exe が完成する。
Linux 上でテストするには、pthreadGC2.dll を sdpa-7.3.2 にコピーしてきて
$ wine ./sdpa.exe example1.dat-s example1.result
である。

これを最終的に Windows に持っていくには、
$ nkf --windows param.sdpa > param.sdpa.windows
$ nkf --windows example1.dat-s > example1.dat-s.windows
として windows 用のテキストファイルにしてから、
sdpa.exe, pthreadGC2.dll, param.sdpa.windows, example1.dat-s.windows を Windows にコピーし、param.sdpa.windows を param.sdpa, example1.dat-s.windows を example1.dat-s にする。
最後にWindows のアクセサリにあるコマンドプロンプトからディレクトリを移動しておき、
sdpa.exe example1.dat-s example1.result
で実行できる。

ここまでで気がついたと思うが、この場合、 reference-blas に接続しているので、ATLAS,GotoBLAS などの性能は出ない。
ATLAS は mingw だとやはりうまくコンパイルができず、GotoBLAS はコンパイルと実行はできるがライセンスの関係で配布できない。

いずれにしても、この程度まで頑張れば、Windows 用のバイナリを生成できる。

2010年10月22日金曜日

semidefinite embedding の論文の読み込み

semidefinite embedding 関係の論文を2本チェック。

[1] Colored Maximum Variance Unfolding
by L. Song, A. Smola, K. Borgward, A. Gretton
[2] Fast Graph Laplacian Regularized Kernel Learning via Semidefinite-Quadratic-Linear Programming
by X. M. Wu, A. M. So, Z. Li, S. R. Li

[1] は、空間ベクトルの他にもうひとつラベル分けが入力情報として得られるときの embedding である。基本的には、ラベル分けの情報が使える分、目的関数に組み込まれている。
あと、Hilbert-Schmidt Independt Criterion というキーワードもあり、これは使えそうである。

[2] は、ずれを最小化する項を目的関数に入れたときに計算量が大きくなるが、SDP に定式化しているものを一部、SOCP で表現できることに着目して計算量を抑えている。アイデア勝負と言って単純な感じなので、学生が書いたものかもしれない。

あと、[2]については、データ生成の元になっている URL が6ページ目に掲載されている。
http://www.cs.toronto.edu/~roweis/lle/code.html
http://www-stat.stanford.edu/~tibs/ElemStatLearn/
これについては、あとで調べることにする。

今日の作業内容:
6:30-7:30 [ok] semidefinite embedding 論文チェック
8:15-8:45 [ok] SparsePOP の confiugure 調整

13:30-14:00 [ng] SparsePOP の configure 調整
14:00-14:30 [ok] SparsePOP の configure 調整
14:50-16:00 [ok] 楕円計算メモ更新
15:20-16:00 [ok] semidefinite embedding の論文読み(一つめ)
16:20-17:00 [ok] semidefinite embedding の論文読み(ふたつめ)の前半
17:00-17:45 [ok] semidefinite embedding の論文読み(ふたつめ)の後半

今日のBGM: FF5 OST [1-2]
今日のランチ:味庵 炸醤麺
明日の予測作業時間: 4h

2010年10月21日木曜日

ドイツホテル予約と semidefinite embedding の論文読み

今朝のうちに semidefinite embedding の論文をチェック。
読んだのは、
K.Q.Weinberger, L.K.Saul, "Unsupervised Learning of Image Manifolds by Semidefinite Programming", Intl. J. Comp. Vision, 70(1), 77-90, 2006

定式化はセンサーネットワーク問題と同じ制約で、目的関数が異なる。
問題設定の関係から、かなりの疎性が見込まれるので、SFSDP で高速に解ける可能性あり。

ただ、探していた方向とはちょっとずれたか。
なお、semidefinite embedding は、他の専門用語でも同じ内容があるようなので、それについてはあとで調べたい。

あと、ドイツのホテルを予約。
複数人数なのでシングルベッドを複数あるところを検索しようとするが、ダブルルームばかりでツインルームが少なく、かなりてこずる。
それぞれのホテルのサイトまで確認して写真をチェックしないとダブるかツインか解らないのが大変だった。
結果的には、それなりのホテルを安く泊まれそうなので、これまでの検索時間は無駄でなかったと考えている。
予約を取るまでに、市内の便利な地域、交通路、治安関係など、実は12時間以上調べている。

今日の作業内容:
6:15-6:45 [ng] semidefinite embedding の論文読み p79-p85
6:45-7:15 [ng] semidefinite embedding の論文読み p81-p85
8:45-9:15 [ok] semidefinite embedding の論文読み p83-p89

10:45-11:30 [ok] SparsePOP インストール確認
13:20-14:00 [ng] ドイツホテル選択
14:00-14:40 [ok] ドイツホテル選択続き
16:30-17:30 [ok] ホテル予約
明日にまわす semidefinite embedding の情報集め

今日のランチ:いろは カキフライ
明日の予測作業時間:4h

2010年10月20日水曜日

Lassere の論文読みと semidefinite embedding

今日は午前中のうちに、多項式最適化の SDP緩和の基本である Lassere の論文を復習しておいた。

有名どころなのではあるが、いちおう書いておくと
J.Lassere, Global Optimization with polynomials and the problem of moments, SIAM J. OPTIM., 11(3), 796-817
である。
この論文の中で特に重要なのは定理 3.2 であり、これによって SDP 緩和が多項式最適化に使えることの根拠となっている。定理 3.2 は1変数のものであるが、多変数についても定理 3.2 の証明と似たような流れを使うことになっている。

あと、他に検索していたところ、semidefinite embedding というキーワードを発見。
なにか関係があるのか、ベースとなっている論文を見つけてきて読みはじめたところである。


今日の作業内容:
5:30-6:30 [ng] Lassere の論文読み P796-808
10:40-11:40 [ok] Lassere の論文読み P805-P810
11:30-11:50 [ok] メモの内容の確認
13:00-13:20 [ok] semidefinite embedding を調べる
16:00-17:00 [ok] semidefinite embedding の論文読み 第1部
今日のランチ:角笛 オムライス
明日の予測作業時間:3h

2010年10月18日月曜日

英語の原稿チェック

海外出張も終了し、今日からほぼ通常業務に復帰。
今日は添削に出していた英語の原稿が返却されていたので、TeX ソースに反映させる。
これを明日のうちに、再度チェックする予定。


今日の作業内容:
11:15-11:45 [ok] 英語の校正を反映
13:00-13:30 [ok] 英語でのメール返信
13:20-13:40 [ok] 国内出張書類確認
13:40-14:50 [ok] 英語原稿のチェック第一部
今日のランチ:シッダルータ 豆のカレー
明日の予測作業時間:6h

2010年10月17日日曜日

IPAM Workshop 2010 [番外編/8]

ここでは、番外編と称して、少しだけ観光してきたところの写真を掲載しておく。

今回は時間がないこともあって、場所が近いところを優先し、ゲッティセンターとハリウッドである。


ゲッティセンターは、UCLAからだと761番のバスである。平日は15分間隔、休日は25分間隔であり、事前にインターネットでバスの時刻表と路線図を入手しておくとわかりやすい。
なお、バスは1回の乗車で1.5$であり、基本的にはおつりがないように準備しなければいけない。
(ただ、一度だけおつりがない乗客がいて、その乗客は2$支払おうとしたけど、運転手は1$でOKにしていた。なかなか粋な運転手である。)

あと、UCLAの近くは 761番と2番が同じバス停に来るので、ちゃんと番号を確認するか運転手に聞いてみたほうがよい。
UCLA の近くからゲッティセンターまでは、およそ15分から20分程度の乗車である。
バスを降りて道の反対側にゲッティセンターに行くトラム乗り場があり、トラムに乗って5分でついにゲッティセンターである。





ゲッティセンターはエントランスビルと 東西南北4つのパビリオンがある。
エントランスビルにはひっそりとゲッティの像が置いてある。


4つのパビリオンが主力の展示施設であって、それぞれの建物が2階建て(西パビリオンは地下もあるる)で、広さの割りにコンパクトに次々と見ていくことができる。
様々な種類の展示が、おおまかには北⇒東⇒南⇒西の順で年代ごとに配置されている。

中には昔の本などもあるが、なんて書いてあるのかは読めなかった。


あと、ヴェネツィアの絵画もあり、これはかなりの大きさで綺麗であった。



カフェもトラム降り場の近くに設置されており、タコスやハンバーガー、グリルなどが食べられる。
今回はタコス2個セット(7.5$), ポテトチップ(1.65$),水(無料)で消費税つきで9$程度である。
タコスは見た目よりもボリュームがあったし、ソースがおいしかった。
ポテトチップは、マスタードにつけて食べてみたら案外マッチしていた。

なお、ゲッティセンターにはガーデンもあり、ここは色々な花で囲まれていて綺麗である。
近くには散歩がてら来ている親子もいる。
(ゲッティセンターは、入場料が無料である。ただし、車の場合は駐車代金が別途かかる。)

ゲッティセンターには研究施設もあり、中には図書館もある。一般の人は入れないが、最上階から図書館の様子を見ることができる。さすがにゲッティセンターだけあって、図書館のデザインも素晴らしい。


ゲッティセンターともう一箇所訪れたのがハリウッドである。
UCLA の近くからだと2番のバスである。
なお、UCLAの近くはロサンゼルスのメトロバスの2番とブルーバスの2番があるので注意が必要である。
この場合はメトロバス(黄色いバス)の2番に乗って、Sunset & Highland で降りることになる。片道が約30分の乗車である。2番はバス停が非常に多く、だいたい200m間隔であるので、どこで降りたいのかを運転手に言っておいたほうがいいし、あらかじめインターネットでどんなバス停があるのかを確認しておくのも良い。
なお、Sunset 通りを2番のバスは通るが、これは Hollywood 通りのひとつ南の通りであるため、運転手に「ハリウッドに行きますか?」と聞いてもダメであり、「Sunset & Highlandの交差点に行きますか?」と聞く必要がある。

なお、Highland 通りから北に移動すると以下の写真の角度で Hollywood 通りに到着する。


近くのお土産屋さんにはエルビスプレスリーなども置いてあったりするし、オスカー像を模した像もお土産用にあり Best wife や Best friends などと書かれている(下の写真だと、右奥の女性が見ているもの)。このオスカー像は Hollywood のなかでも Highland street のあたりが一番高く、Highland から離れると1$程度安くなる。


ここが Hollywood & Highland のショッピングセンターで、ハリウッドの中心的な位置。ここの中央の階段から、有名な「Hollywood」の文字が、驚くほど小さく見える。(かなりの望遠カメラでないと綺麗に撮影できないほど小さい。)




ショッピングセンターの左隣は Kodak Theatre であって、アカデミー賞の会場である。



あと、チャイニーズシアターはハリウッドのシンボルとして有名である。実際に映画も上映されているが、今回は時間の関係で見ることが難しかったので、どんな映画かもチェックしてこなかった。



なお、ハリウッドの通りには有名人の星型がある。Kodak Theatre の前には、マイケルジャクソンやミッキーマウスなどの有名人のものがある。おかげで下を見てばかりになるので、安全に注意が必要でもある。




あと、チャイニーズシアターの前には有名人の手形もあり、エディマーフィーやダースベーダーの手形などもある。どこにどの手形があるかは、地球の歩き方に詳しい。


Kodak Theatre の中は、こんな感じである。


この日は、お昼を Hollywood & Highland の中のレストラン、The Grill で食べてみた。
パスタとサラダのセットで、チップまで込みで 17$程度。
サラダはボリュームがあるが、パスタはそれほどでもないので、十分に食べきれるボリュームだし、味もよかった。

お店はこんな感じの雰囲気である。



ハリウッド通りをかなり東に歩いていくと、途中の路地のところで有名な壁がある。
有名人がたくさん写っていて見ていると楽しくなる。
全体の写真を撮るときは道向かいからの撮影になるため、車が通っていない隙間を狙う必要があり、これがなかなかに難しい。

壁画から Hollywood & Highland に戻る途中には、さりげなくエジソンの星型もある。
(俳優だけでなく、映画関係者や音楽関係者のものもある。)

Hollywood & Highland に戻ったら、霧が晴れていて HOLLYWOOD の文字をはっきりと見ることができた。デジカメで最大に拡大して撮影をしてみた。

ちなみに、周りの風景も入れると以下のような感じであり、文字が小さいことが良くわかる。

ハリウッドは意外と見るものがないので、2時間もあれば要点をチェックできる。
ゲッティセンターは見るものが多いので、できれば半日は欲しいところだ。