SDPARA-C と TSPLIB

TSPLIB に pcb1173 という問題があるが、これが手頃な大きさなので delaunay グラフ(添付の図を参照)を作って、max cut 問題に対する SDP 緩和問題を作る。何故こんなことをしているかと言うと現在 SDP の疎性に関する研究を行っているからである。疎性を利用する → Schur complemet 行列が疎になる → conversion や completion が効を奏する → 疎性を利用して高速に計算できるようにデータの並び替えやパッキングを行うという流れにしたいからである。これを SDPA と SDPARA-C で解いてみよう。

1: SDPA 7.2.0 + GotoBLAS 1.26 (1スレッド)
1m7.477s (16反復)
2: SDPA 7.2.0 + GotoBLAS 1.26 (8スレッド)
19.216s (16反復)
3: SDPARA-C 1.0 + GotoBLAS 1.26 + ATLAS 3.8.2 (16CPU × 1コア)
4.845s (21反復)

というわけで、この種の sparse な問題では SDPARA-C の圧勝である。相当 completion が効くみたいである。