以下のように SCM(Schur Complement Matrix)が疎になるときの計算については、効果が薄いということでこれまでは見送ってきたのだが、様々な変更によって効果も見込めるようになってきた。これからも様々な ○問題 mater-4.dat-s SDPA 7.3.3β (SCM シングルス…

最新の MIP ソルバーを入手して簡単な比較実験を行った。やはり CPLEX と Gurobi が２強となっている。他のソルバーにおいて１時間以内に問題が最適に解けなかった場合では、(下界, 上界) を記しておいた。 ○問題 S-20-20-2-3.mps（ロットサイズ決定問題）: …

ILP64 (int型 = long型 = ポインタ = 8bytes) 対応の SDPARA を作成してみた(まだ完成はしていない）。単に int を long long int 置き換えるだけでなく、関連するライブラリなどの対応も必要であるので、結構面倒な作業である。これまでの SDPARA は LP64 (…

実験結果が多いので二つに分割した。前回の続きになる。プロセス数が増加するのに従って TEPS 値も上がっていくのだが、現在の実装では construction_time が大き過ぎる。 ○プロセス数 = 8 SCALE: 18 edgefactor: 16 NBFS: 64 graph_generation: 5.38377 s n…

新クラスタ計算機において SCALE = 18 に設定して、Graph 500 のリファレンス実装(graph500_mpi_simple)の実行を行った。プロセス数を 1 から 32 まで変化させている。 ○プロセス数 = 1 SCALE: 18 edgefactor: 16 NBFS: 64 graph_generation: 5.39078 s num_…

様々な中心性(Centrality)の指標がある中で、こちらのクラスタ計算機を用いて DIMACS 全米データの Betweenness Centrality (BC) の計算を行っている。これらの計算を１台の計算機のみで行うのはさすがに厳しいものがある。スパコンが必要とまでは言わないが…

SDP は元問題の種類や特性によって以下のように Schur Complement Matrix (SCM) が密になったり疎になったりする。 左のように SCM が密になる場合では SCM の各要素の計算において行単位でのマルチスレッドの計算が非常に有効だが、右のように非常に SCM が…

3月19日に2011年度第１回 SCOPE を開催して以下の２件の講演を行います。是非ご参加下さい。OR学会の春季大会の直後(次の日)に行います。 ○2011年度第1回 SCOPE 日 時 ： 2011年3月19日（土）14:00～ 会 場 ： 中央大学 後楽園キャンパス 3 号館 3300 号室（…

先日紹介した以下の多項式関数最小化に関する SDP 緩和問題は以下の通りになる。 f(x, y) = x^4 + 2y^4 - 2x^2y^2 - 2y^2 ファイルはこちらのリンクから入手可能。SDPA のバイナリが無ければ SDPA Online Solverから実行することもできる。ただし、先日報告…

以下の DIMACS 全米データを含む様々なグラフの Centrality(中心性)の並列計算をクラスタ計算機を用いて行っている。ただし、空調機の調子が依然として悪い（修理部品の取り寄せ中）ので、安定して最後まで終了するのかはわからない。 以下の中心性の指標を…

持ち込みで以下の多項式関数の最小値を求めたいという話があった（実際にはこれはサンプルなのでもっと大きな問題を解きたいらしい）。 f(x, y) = x^4 + 2y^4 - 2x^2y^2 - 2y^2 ただし、以下のようになるので最小値は -1 になる。 f(x, y) = (x^2 - y^2)^2 +…

2月26日に第５回 SCOPE を開催して以下の２件の講演を行います。是非ご参加下さい。 ○2010年度第5回 SCOPE 日 時 ： 2011年2月26日（土）14:00～ 会 場 ： 中央大学 後楽園キャンパス 6 号館 講演1 講演者 ： Thorsten Koch氏 （Zuse Institute Berlin(ZIB),…

学生に対する演習で以下のようなサイズの MIP を作成した。 38 rows, 764 columns, 2803 non-zeros, 760 integer variables そんなに簡単な問題では無いと思っていたのだが、やはり GLPK (4.45) では簡単に解くことは出来ない。6分たっても上界と下界の差は…

以下のシンポジウムが 2月16日に開催される。参加には事前登録が必要となっている。 2010年度理研シンポジウム ペタフロップス時代のセンターシステム 2012年に運用が開始される「京」の構築が進む中、国内外でペタフロップス規模のシステムの運用が始まって…

Debian の unstable (sid) から SDPA の パッケージ 7.3.4 を apt-get でインストールすることができる。 パッケージ: sdpa (7.3.4.dfsg-1) Debian パッケージの都合で SDPA も正式公開版からバージョンアップが続いてすでに 7.3.4 になっている。 同じマシ…

超巨大 DNN 緩和問題に挑戦する前にいろいろなデータを取っているが、QAP の場合では制約条件が単純なので DNN 緩和問題に変換したときに制約条件の数(SCM のサイズ)は膨大になるが、制約行列の数はあまり大きくならない。そのため以下の結果のように SCM の…

あまり大きく無い DNN 緩和問題を解いてみて、最適解と比較を行った。LP による下界値が良くない QAP であるが、DNN 緩和問題による下界値と最適解の目的関数値は相当近くなっている。この DNN 緩和問題を用いて QAP を最適に解いてみるというのは大変な作業…

１：アルゴリズムによる高速化と計算機による高速化が明確に分離（区別）することが出来なくなった. つまり最新のアルゴリズムでは最新の計算機アーキテクチャでの実行を前提としたものが増えてきている． ２：計算量による理論的解析の優劣とソフトウェア実…

新クラスタ計算機上で OpenMPI と MVAPICH2 の両方をインストールして SDPARA の性能を比較しているのだが、前者の方がはるかに性能が良い。あまりにも性能差があるので、MVAPICH2 の方は何か設定等のミスがあるのかもしれない。 ○ソフトウェア SDPARA 7.3.2…

依然として空調機の１台が不調のままで、先日の修理後はほとんど動作しなくなったので、一応動作はしていた修理前よりも状況は悪化した。冬の寒い時期なので何とか各サーバも停止しないで動作しているのであるが、暑い時期であれば相当数のサーバを停止させ…

こんなクラスタ計算機を見付けました。インストールされているソフトウェアを見ると SDP 専用のクラスタ計算機らしいですが、世界中で SDP のソフトウェアが利用されているのは好ましいことです。並列計算の敷居は低くなってますので、積極的に SDPARA 等も…

日本オペレーションズ・リサーチ学会 2011年春季研究発表会の発表申し込み締め切りが１月１１日に迫って来ました。以下のように SCOPE でも特別セッションを予定しています。本当は複数セッションにしたかったのですが、様々な事情により出来ませんでした。…

以下の計算サーバ上に VMware Player を用いて次のような環境の仮想マシンを起動させた。 コア数： 4 メモリ： 32GB SDPA 7.3.3βでは 7.3.2 と比較して仮想マシン上での性能向上が達成されている。 ○問題 LiH.1Sigma+.STO6G.pqgt1t2p.dat-s 1: SDPA 7.3.2 : …

以前にも紹介したように Betweenness Centrality (BC) という指標は、以下のように最短路問題(Shortest Path Problem : SP)を複数回（厳密には全対全)解くことによって求めることができる。グラフが規模が大きくなると全対全最短路問題(All-Pairs Shortest P…

以下はこのブログでも何回も用いている QAPLIB の esc32a に対する DNN 緩和問題である。この非常に大きな SDP を用いて比較実験を行っている．CHOLESKY の方は BLAS の性能で決まるので，ELEMENTS の性能で全体の性能も大きく左右される． 102208 = mDIM 14…

首都高速の３号線と中央環状線をつなぐ大橋ジャンクションは高低差７１ｍで屋内（あるいは地下）で２回転ほど回る仕組みになっている． 首都高速 中央環状線 大橋JCT～西新宿 GPS以外の測位システムを持たないカーナビではこの大橋ジャンクションを通って地…

LAPACK に DPOTRF という Cholesky 分解を行う関数がある。某ソフトウェア(SDPAではない)で見かけたのだが、INT型 = 4bytes のまま LAPACK, BLAS をコンパイルして要素数が INT 型の最大数を超えるベクトル A を DPOTRF 関数に渡しているのだが、これで大丈…

今年の２、３月の SCOPE 研究会は以下の日程と内容で行う予定です。詳細が決まり次第、Web から情報を公開します。 ○2010年度第5回 SCOPE 日 時 ： 2011年2月26日（土）14:00～ 会 場 ： 中央大学 後楽園キャンパス 6 号館 講演1 講演者 ： Thorsten Koch氏 …

Intel Xeon Westmere-EP (2-way) と AMD Opteron Istanbul (4-way)の性能比較を行っているが、その一部を掲載する。コア数では後者が２倍なので総合性能ではわずかに上回っているが、やはり Westmere-EP の性能の良さが目立っている。 ○問題 esc32a_r2.dat-s…

現場を見た訳ではなく、遠隔からログインしているだけなので詳しいことはわからないのだが、以前から不調の空調機（１台）が停止しているようだ。以前、こちらに記したようにクラスタ計算機等の一部を停止しているが、数値実験を行っていたサーバで停止（暴…