疎行列の計算

 Eigenの動きを見ると,大規模インスタンスでは、勝手にマルチスレッドで動いています。しかしながら、バリアソルバと比べると未だバリアソルバの方が速いという結果です。予想外でした。

そもそもFirstOrderの利点としては、matrix-free (逆行列計算を必要としない）にあります。(Simplexにしてもバリアソルバにしても、疎行列の逆行列計算は、ほぼ必然といってよいと思います。)　利点部が逆にネックになっているというのは予想外でした。

良く調べていないのですが、ボトルネックは、規模から言ってベクトル演算部分ではなく、行列計算部であると思います。そこで、疎行列の積和演算に関しては、Eigenを使わずに自作することにしました。

まずは、疎行列演算規模の見積もりです。Branch＆Bound処理に行く直前の行列規模です。

nは、変数の数、mは、制約の数です。内ゼロでない係数が1.6-2.7%程度あるという結果になりました。やはり疎行列処理をすることが正しいという結果になりました。

instance21で、全体項数が625676　あり、行列xベクトル演算が2箇所、収束までIteration100000、全体での実行時間は、演算速度を1nsとすると

625676*2*100000*1e-9=125秒

となります。これがSingleThreadでの理論値になります。このままでは、バリアソルバでの実測値　75秒(Simplexでは数分かかるので論外）より大分劣ってしまいます。しかし、これから、SIMD化＋マルチスレッド化による性能向上は見込めるので、上手く実装できれば、バリアソルバの数倍、GPU実装では、さらなる効果が期待できます。(GPU実装は予定しません）

いずれにしても現在の状態を改善しない限り、1週間以上計算機を廻さないかぎり解が得られないので、高速化は必須です。