トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –

Presentation on theme: "トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –"— Presentation transcript:

1 トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
東京大学　情報理工学系研究科 中山 裕貴 December 15, 2003

2 発表の背景 グレブナ基底の計算方法 F4,F5とは この２つの算法により、今まで解けなかったサイズの問題が解けたと言われている
従来はBuchbergerの算法およびその亜種 （改良は主に、不要なペアを除く手法について） F4,F5とは Faugèreによる、グレブナ基底計算の新しい算法 F4[Faugère ‘99] ･･･ 多項式同士の計算を、まとめて行列の形で行う F5[Faugère ’02] ･･･ 新しい多項式を追加するとき、 以前の計算結果を部分的に保存しておく この２つの算法により、今まで解けなかったサイズの問題が解けたと言われている

3 発表の内容 今回は、対象をトーリックイデアルの場合に限定、 アルゴリズムを専用に特化させる アルゴリズムはasir上で実装・評価
F4アルゴリズムを改良し、高速化・メモリ節約 このとき、簡約操作を非常に効率よく行うことができる F5アルゴリズムを新たに実装 上記２つのアルゴリズムについて、２つの異なる 項順序で実行時間を計測 実行時間の解析のため、計算途中における sugarや次数、およびペア数を比較する アルゴリズムはasir上で実装・評価

4 トーリックイデアルとは 多項式イデアル を考える トーリックイデアル は行列 で定まり ならば、 および多項式 について、 例:
係数k は体,k[x1,x2,…xm]は多項式環 多項式イデアル　　　　　　　　　　　を考える 　　　　ならば、 　　および多項式 　について、 トーリックイデアル　　は行列　　で定まり を満たす二項式イデアル (係数は1,-1) をこう書く 例: のトーリックイデアルは 線形代数でいう核の次元(=2)より多い

5 単項間の順序関係 任意の単項m1,m2に対し、順序関係を定める 多変数の場合、順序は一意ではない 整列順序であり、最小元は ならば、
　　　　ならば、 多変数の場合、順序は一意ではない 辞書式順序 全次数逆辞書式順序 で最も左の非零要素が正 def あるいは かつ def で最も右の非零要素が負 多項式　中で、順序　で最大となる項を 　　　　と書く

6 グレブナ基底とは イデアルI に含まれる多項式に対し、 その先頭項で生成されるイデアル を考える 一般に、イデアルI の生成元 について
しかし、生成元　　　　　がグレブナ基底のとき またそのときに限って 例: イデアルに対し、簡約グレブナ基底は一意に定まる

7 グレブナ基底を求める Buchbergerのアルゴリズム
入力: イデアルの生成元 出力: グレブナ基底 do { 　　　　 ; Gの任意のペア(i ,j )に対し、Spol(gi ,gj )を計算; 　Spol(gi ,gj )をGの要素で簡約したものをg’ とする; g’ が0でなければ、Gに加える; } while(　　　　) S多項式:　　　　　　　　　　　　　　として のこと Gの要素で割り、剰余を求めること 問題点: ペアの数が膨大になる 簡約に時間がかかる

8 Buchbergerアルゴリズムの 主な改良法
計算不要なペアの除去 簡約の高速化 併用可能 頭項の比較により、 0に簡約されるペアを一部除く あらかじめS多項式を複数生成し、 行列の形式で一度に簡約する F4アルゴリズム Buchbergerの規準 Gebauerの規準 以前の計算結果を用いることで、 0に簡約されるペアを完全に除く トーリックイデアルに 限定したアルゴリズム F5アルゴリズム 行列Aによって定まる多面体の 構造を利用して求める non-Buchberger アルゴリズム 今回はF4とF5がターゲット

9 F4アルゴリズムの概要 複数のS多項式を計算しておく それらの簡約に必要な元の候補を選ぶ Symbolic Preprocessing
簡約時に加減算だけで済むよう、単項式倍しておく Symbolic Preprocessing Symbolic Preprocessing 入力: 多項式集合F,G 出力: Red = T={F中に出現する全ての項}; Red = { }; while ( 　　なる　　　　　　　が存在) { 　　Redに　　　　　 　を追加; 　　Tからtを除き、　　　　　　 の先頭項以外の項を追加; }

10 F4アルゴリズムの概要 S多項式・簡約に使う元を行列で表す 行が多項式、列が単項の種類を表す
簡約 = 行列の対角化 (多項式の定数倍・加減算) 例: を で簡約 (簡約される元) (簡約に使った元) (簡約される元) 簡約された結果 (簡約に使った元) (簡約に使った元) (簡約に使った元) 0に簡約された 対角化 簡約した結果

11 トーリックイデアルに対する F4アルゴリズム
各行には1,-1が1個ずつだけ、他は0 1 が -1 より左に来る 行列は非常に疎であり、メモリを浪費する 行列 データ構造とアルゴリズムの改善 行列を有向グラフとして表す 列　　　　　　　　を、有向辺 (i, j )とする 行列の変形 = 枝の付け替え 1 2 3 4 1 2 3 4 出次数が２以上 入・出次数が両方１以上 の場合、辺を付け替える

12 F5アルゴリズムの概要 新たに多項式を生成したとき、生成に使った 多項式の情報を保持しておく 例: 入力を としたとき、S多項式
が生成されたとする このとき　　の代わりに　　　　　　　　　を加える は　　　　　　で生成される、という意味 さらに が生成されたとすると、 Ruleとして後で使う の情報を用いて を加える は　　　　　　　で生成される、という意味 さらに が生成されたとすると、 の情報を用いると、これが 0 に簡約されると分かる この判定法を用いる 0に簡約されるようなS多項式を、全く生成しない

13 Buchberger, 改良したF4, F5 のベンチマーク – 実験の環境
入力: 行列　　　　　　　　　　の トーリックイデアルの生成元 項順序 全次数逆辞書式順序 辞書式順序 計算代数システムasir上での実装 ３つのアルゴリズムの比較 組み込みのBuchbergerアルゴリズム (modular計算はしない) 今回改良したF4アルゴリズム F5アルゴリズム　　 CPU : UltraSPARC-II 360MHz, メモリ : 2GB 　 変数順序は

14 ベンチマーク (n=10～40,全次数逆辞書式順序)
実行時間は、 　F4 < F5 < Buchberger の順

15 ベンチマーク (n=10～40,辞書式順序) nが増加するにつれ、改良したF4は、Buchbergerよりも性能が悪くなっていく

16 F4,F5の計算時間増大の原因 辞書式順序でF4,F5の計算時間が増える理由 A20を例に実験を行った結果･･･次ページ
生成される多項式の次数(sugar)が増大 A20の場合、基底の最大次数は 全次数逆辞書式の場合　･･･ 3 辞書式の場合　･･･ 20 F4の場合、簡約行列のサイズが冗長になる? F5の場合、不要なペア・Ruleの数が増大? A20を例に実験を行った結果･･･次ページ

17 F4による A20のグレブナ基底計算の効率 全次数逆辞書式順序 ･･･ 辞書式順序 ･･･ この場合、逆に効率が悪くなる 3 171 17
全次数逆辞書式順序　･･･ sugar S多項式の数 簡約に使う 多項式の数 0以外に簡約された 3 171 17 4 2109 373 0　（終了） 行列演算の利点を 生かしている 辞書式順序　･･･ sugarが大きくなるにつれ、極少数の 多項式を、多数の多項式で簡約しよう としている それに対し、得られる非零な正規形 はただ１つだけ この場合、逆に効率が悪くなる

18 F5 による A20のグレブナ基底計算の効率 全次数逆辞書式順序 ･･･ 辞書式順序 ･･･ 次数４以上の項は生成されない
全次数逆辞書式順序 ･･･　 次数４以上の項は生成されない 生成されたS多項式は、必ず0以外に 簡約される 次数 ペアの数 S多項式の数 3 324 171 （終了） 辞書式順序　･･･ 生成される多項式の次数が大きい 　ものが存在 それにより、次数が大きくなっても 　かなりの数のペアが残り、計算に 　時間を食う ペアの選択が、先頭項のLCMの次数 　(Sugarを使わない) によるのも原因

19 実験結果 組み込み関数とF4,F5の比較 全次数逆辞書式順序では、F4,F5の方が高速 辞書式順序では逆に時間がかかる
F5について、sugarを使う方式に書き換える 今後は ことが考えられる

20 ありがとうございました