ソフトウェア SDPA の実装方式について

我々のグループではこのブログでも述べているように代表的な数理計画問題であるSDP に対する内点法を記述したソフトウェアSDPA の開発・評価・公開を１０年以上行っている. 最近では以下のような開発方針を採用している.

1. 近年のソフトウェアにおいては疎データの扱い, 疎構造の記述方法が重要になっているが, 入力問題に対して自動的に適切な前処理を行い, 密データ構造と疎データ構造のどちらで処理するかについて判断を行う.
2. 通常, ソフトウェアのボトルネックはCPU コア内部(浮動小数点演算能力やL2 キャッシュの帯域幅など) に存在するか, CPU とメモリ間の帯域幅に因るものかのどちらかである場合が多い. この特性を用いて, アルゴリズムの各部分のボトルネック構造を解明することによって適切なアルゴリズムを選択することができる.
3. 数値精度が問題になる場合には, 任意精度演算などを用いて得られる精度と計算時間とのトレードオフなどに注目しながら, 適切な方法を選択していく.