(1) 研究上の成果
通常の体を係数環とする多項式環におけるグレブナ基底の計算において単項順 序のおよぼす影響はきわめて大きいことが知られている。一般に全次数逆辞書 式順序が、計算時間及び計算領域ともに一番小さくなり、一番便利な純辞書式 順序が計算時間及び計算領域ともに一番大きくなる傾向がある。これに対し、 ブール多項式環におけるグレブナ基底の計算においては、逆の傾向すなわち、 一番便利な純辞書式順序が計算時間及び計算領域ともに一番小さくなる傾向が あることが、われわれのおこなった計算実験から判明した。おそらくブール多 項式環における多項式が各変数にたいして次数が高々１までしかないのが主要 な原因と思われる。この点について理論的に解明するのはこれからの課題であ る。また、一番便利な純辞書式順序が一般に一番簡単に求められるので、同次 化の手法が計算の高速化に有効なことが予想される。これに関しても計算実験 をおこなって検討することが望まれる。
外部発表論文リスト
(2) ソフトウェアとしての成果;
集合制約ソルバーのソフトウェアは図 1のよう に５つのプログラム群で構成される。
ユーザは解きたい集合制約を入力する。この集合制約は変換プログラムによっ て集合ブール環上のブール多項式環を係数ブール環とするブール多項式環(以 下BR1と記すことにする)のいくつかの多項式に変換される。
これは主要エンジン部に渡され、これが生成するイデアルのグレブナ基底(BR1 における)が計算される。
計算されたグレブナ基底の定数部(BR1における)を用いて要素変数を解かなけ ればならないが、この部分はいったんユーザーに引渡される。
引き渡される出力から要素変数についての(特殊)解は容易に得ることができる ので、ユーザーが特殊解をここで入力するといったインタラクティブなやり方 がよいという結論に達しこの方針で開発を行った。
システムの要素変数ソルバーは、入力された解が正しいかどうかのチェックの み行う。正しい入力にたいしてソルバーはその値を前に求めておいたBR1にお けるグレブナ基底へ代入する。
BR1におけるグレブナ基底は、基本的にはBR2におけるcomprehensiveグレブナ 基底なので、代入した結果はBR2におけるグレブナ基底になっている。この結 果を用いて解生成プログラムでは、解きたい集合変数について整理して、その 結果を一般解として出力する。さらに、ソルバーは個々の集合変数が実際にど のようになっているかのチェックも行う。
図 1. 集合制約ソルバーのソフトウェア構成
以上が集合制約ソルバーのソフトウェア構成の概要である。
主要エンジン部の二つのソルバーは、それぞれ単独でユーザーが使えるように もなっている。これを用いて、ユーザーはわれわれが開発した一風変わったグ レブナ基底についての数学的実験(グレブナ基底およびcmprehensiveグレブナ 基底の計算、イデアルの変数消去、剰余類の代表元の計算等)を楽しむことが できる。
前年度に prolog で作成したソルバーでは、SICStus prolog の fast codeモー ドで コンパイルすると 、上に述べた問題は、東芝ワークステーションAS4080 で、１０秒程度で解けていた。今年度 klic で作成したソルバーでは同じ環境 で３秒ほどで計算が終了する。問題の程度が小さいときは、このように性能は ３倍程度の高速化になっているが、さらに問題が大きいときは、klic 版のソ ルバーの方がはるかに高速である。prolog版で１０５分かかる計算で逐次版 klicで３分３０秒という結果も出ている。われわれのプログラムはほとんど変 わっていないので、われわれの成果ではなく単にklicが高性能であることがあ らためて実証された１例であると思われる。
プログラムサイズ
klic で 約2000行
ドキュメント
グレブナ基底解説書、マニュアル
(3) 残された課題
制約論理型言語GDCCのソルバーとして使うための開発は今後の課題である。
(4) 自己評価
ソルバーに用いたグレブナ基底は、われわれのオリジナルであり、世界でも例 のないユニークなソフトウェアになっていると確信する。