(9)集合制約ソルバー　

研究テーマ、研究代表者：

(1)研究テーマ

(2)研究代表者(氏名、所属、役職)

報告項目

(1) 研究の目的

集合制約ソルバーのメインエンジンは集合ブール環上の多項式環におけるグレブナー基底の 計算プログラムである. このプログラムは特殊なモノミアルリダクションを利用した アルゴリズムを用いて作成されている. 最近、研究代表者らの研究によって、このような多項式環上のグレブナー基底が GF(2)上の多項式環におけるグレブナー基底の計算を利用した並列アルゴリズムによって 求められることが明らかになった.

本研究では、集合制約ソルバーのメインエンジンのグレブナー基底計算プログラムを、 この並列アルゴリズムを用いたものへ書き換える. これにより、PVMをによる並列版KLICによる並列計算による高速化が実現される. 逐次環境においても従来のものよりはるかに高速なプログラムが得られる.

(2) 研究の進捗状況

集合ブール環上の多項式環におけるグレブナー基底計算の逐次版プログラムはほぼ完成された. 並列版も同時に作成していて、一応動くものができているのだが、プロセス通信の負荷が異常に重たい. 単体の計算機でプロセスが１つしか走らせていない場合においてすら出力が異常に遅くなってしまう. アルゴリズムのメインな部分は複数台の計算機による並列計算でも、確かに高速に計算が実行されて いるようなので、各プロセスで計算されたGF(2)上の多項式環におけるグレブナー基底をマージして、 集合ブール環上の多項式環におけるグレブナー基底を再構成させるところに問題があるようである. 逐次版ではこの部分のコストは微小なので、プロセス通信になんらかの問題があるようである. これに関して現在試行錯誤を繰り返しているところである.

(3) 現在までの主な成果

逐次版においては期待していたような高速なグレブナー基底計算プログラムが得られた. ただし、これは十分予想できたことなのだが、各要素変数に対して集合制約がほとんど一致するような 場合においては(このようなケースは非常にまれなケースであるが)、逐次版では逆に遅くなってしまう ことを再確認した. スムーズに動作する並列版が完成されないとこの点は改善されない.

(4) 今年度目標成果ソフトウェアイメージ

新しいアルゴリズムにより、高速なグレブナー基底計算プログラムが得られ、集合制約ソルバーも より短時間で計算を終了できるようになる. さらに、並列版KLICを利用できる環境においてはいっそうの高速化が実現される.