ホモトピー法

現在 SDPA クラスタで、多項式方程式系の全解探索のためのホモトピー法の実験をしている。
アルゴリズムは３つに分かれていて、
1: Mixed Volume の計算
2: Homotopy path の追跡
3: 解の検証
になる。今は一番時間がかかる 2 の検証実験を行っている。

K 研の博士課程 G 君が、そろそろ博士論文を仕上げないとならんということなので、並列実験の論文を書くために実験をしている。ホモトピー法の研究も一段落と思っていたら、K 研に一度企業に行った M 君が博士課程として戻ってきた。上記の 1 の Mixed Volume の計算をさらに高速化させたようで、以下の連絡をいただいた。

----------------------------------------------------------------------
一方、現在、開発中のプログラムでは、以前作成したプログラムと
ほとんど同じ問題を扱っています。工夫している点は、これまでに作成した
列挙木の情報を利用して、将来、ノードになりうる候補の個数を限定しています。
それと同時に、LPの構造を利用して、列挙木のレベルが深くなるにつれ、
各ノードで解くLPのサイズ(次元、式の数)が小さくしていくことが可能です。
なお、Gao-Liが利用しているRelation Tableも使っています。

その結果、解かなければならないLPの個数を減らすことと、そのLPの規模を小さく
することで、高速化が実現されました。
----------------------------------------------------------------------

K 先生によると、Ninf で並列化されたホモトピー法の公開を待っている人がいるそうだ。
思ったより盛り上がっていて、面白くなってきました。