9.集合制約ソルバー

［目次］

1. ブラッシュアップ対象ソフトウェア名称
2. 体制／方法
3. 想定されるブラッシュアップ成果

［ブラッシュアップ対象ソフトウェア名称］

• 集合制約ソルバー

［体制／方法］

(1) 体制

	氏名	所属
研究代表者	佐藤洋祐	立命館大学理工学部情報学科
研究協力者	高山幸秀	立命館大学理工学部情報学科
研究協力者	三橋元洋	立命館大学大学院理工学研究科
研究協力者	天野　淳	立命館大学大学院理工学研究科
研究協力者	山崎栄二	立命館大学大学院理工学研究科
研究協力者	西川寛人	立命館大学理工学部情報学科
研究協力者	山口　淳	立命館大学理工学部情報学科

(2) ブラッシュアップの方法

　平成７年度及び８年度における委託研究として、ブール環上の多項式環におけるグレブナー基底に基づく集合制約ソルバーの作成をおこなったが、その後提案者はブール環の拡張である Von Neumann regular ringにおいても、われわれのグレブナー基底に関する結果が拡張できることを証明した。これらの結果は、今年の８月に開催される計算機代数の国際会議 ISSAC'98(International Symposium on Symbolic and Algebraic Computation)で発表される。(http://wwwteo.informatik.uni-rostock.de/ISSAC98 参照)この中で証明された結果の一つを用いると、集合ブール環上の多項式環におけるグレブナー基底が、係数環の全体集合の要素の個数を n としたとき、最も単純なブール環である {０,１} 上の多項式環におけるグレブナー基底の計算を n 回行うことによって計算することが可能になる。この計算方法はブール方程式の解法に、ノントリビアルな並列計算の可能性をもたらす画期的な方法である。

実際のインプリメントにおいても、従来の方法とは比べものにならない程のスピードアップが期待できる。というのも、この n 回の計算は、完全に独立した分散計算であり、しかも {０,１} 上の多項式環におけるそれぞれのグレブナー基底の計算は、もとの集合ブール環上のグレブナー基底の計算よりもはるかに小さい計算時間で計算可能になるからである。{０,１} 上の多項式環におけるグレブナー基底の計算は平成８年度に作成したプログラムでも実行可能である。これを用いて、手動でおこなったシミュレーションでは、問題の規模にもよるが、{０,１} 上の多項式環におけるそれぞれのグレブナー基底の計算は、もとの集合ブール環上のグレブナー基底の計算よりも、はるかに小さい計算時間(実験では n = １０ のとき 約１／１００、n = ３０ のとき 約１／１０００)で計算可能になる。しかも {０,１} 上の多項式環におけるそれぞれのグレブナー基底の計算はほとんどが同程度の計算時間になり、特別に長時間必要な計算は現れない。今回のブラッシュアップでは、平成８年度に作成したプログラムを書き換えることで、この分散計算を KLIC の言語仕様を利用した自然な形で実現させたい。上述のように単一計算機でも、十分なスピードアップが見込まれるが、PVM 等を利用した並列計算環境において、ほとんどリニアーな台数効果が期待できる。

［想定されるブラッシュアップ成果］

1. ブラッシュアップ項目

   • 操作説明書や例題集の拡充
     　グレブナー基底の計算アルゴリズムが並列アルゴリズムへ変更されるが、従来のものもそのまま残すことで両者の差が実感できるように、いろいろな例題を拡充する。また、並列計算のための操作説明書も新たに作成する。なお、集合制約ソルバーについては、計算速度の画期的短縮が予想されるが、操作に関しては従来のものと全く同じである。

   • プログラムや用いられたアルゴリズムの解説の拡充
     　アルゴリズムの理論的バックグランドとして、Von Neumann regular ring 上の多項式環におけるグレブナー基底の理論と、これを用いてどのようにして集合ブール環上の多項式環におけるグレブナー基底を計算する分散アルゴリズムが実現されるのかについての解説を新たに作成する。

2. 上記のブラッシュアップによるユーザの立場からみた改善点

   　まずいえるのは、画期的に速くなることである。逐次計算でも従来のものよりもはるかに高速化される。さらに、アルゴリズムが完全に独立した分散計算であるので、並列計算を実行できる環境においては、利用者は、リニアーに近い台数効果を得ることができる。

3. 上記のブラッシュアップ以外のソフトウェア機能の改良

   　集合ブール環上の多項式環におけるグレブナー基底の計算アルゴリズムを Von Neumann regular ring 上の多項式環におけるグレブナー基底に関する提案者の理論に基づいた並列アルゴリズムに書き換える。このアルゴリズムは、ブール方程式の解法においてノントリビアルな並列計算の可能性をもたらす画期的な方法である。