トーリックイデアルの
グレブナ基底を求める
アルゴリズム – F4およびF5 –
東京大学 情報理工学系研究科
中山 裕貴
December 15, 2003
発表の背景
グレブナ基底の計算方法
F4,F5とは
従来はBuchbergerの算法およびその亜種
（改良は主に、不要なペアを除く手法について）
Faugèreによる、グレブナ基底計算の新しい算法
F4[Faugère ‘99] ･･･ 多項式同士の計算を、まとめ
て行列の形で行う
F5[Faugère ’02] ･･･ 新しい多項式を追加するとき、
以前の計算結果を部分的に保存しておく
この２つの算法により、今まで解けなかったサイズ
の問題が解けたと言われている
発表の内容
今回は、対象をトーリックイデアルの場合に限定、
アルゴリズムを専用に特化させる
F4アルゴリズムを改良し、高速化・メモリ節約
このとき、簡約操作を非常に効率よく行うことができる
F5アルゴリズムを新たに実装
上記２つのアルゴリズムについて、２つの異なる
項順序で実行時間を計測
実行時間の解析のため、計算途中における
sugarや次数、およびペア数を比較する
アルゴリズムはasir上で実装・評価
トーリックイデアルとは
係数k は体,k[x1,x2,…xm]は多項式環
多項式イデアル I k[ x1 , x2 ,, xm ]を考える
f , g I ならば、 f g I
f Iおよび多項式 h について、hf I
トーリックイデアル I A は行列 A で定まり
I A x u x v | Au Av, u, v N n
x u x1 1 x2 2 x m m をこう書く
u
u
u
を満たす二項式イデアル
(係数は1,-1)
例: A 1 3 1 5
1 2 3
7
2
3
4
3
x
y
z,
x
y
zw,
x
w
y
のトーリックイデアルは
2
線形代数でいう核の次元(=2)より多い
単項間の順序関係
任意の単項m1,m2に対し、順序関係を定める
整列順序であり、最小元は 1 ( x10 x2 0 x 0 )
x u x vならば、x u x t x v x t
m
多変数の場合、順序は一意ではない
辞書式順序
xu xv
def
u1 v1, u2 v2 ,, um vm で最も左の非零要素が正
全次数逆辞書式順序
xu xv
def
u v あるいは u v かつ
u1 v1, u2 v2 ,, um vm で最も右の非零要素が負
i
i
i
i
多項式 f 中で、順序 で最大となる項を in ( f ) と書く
グレブナ基底とは
イデアルI に含まれる多項式に対し、
その先頭項で生成されるイデアルin I を考える
in I in f | f I
一般に、イデアルI の生成元 f1 , f 2 , f n について
in I in ( f1 ), , in ( f m ) 例: I x y, x y , x y
in I x, y , in ( x y ), in ( x y ) x
しかし、生成元 g1 ,, g s がグレブナ基底のとき
またそのときに限って
in I in ( g1 ),, in ( g s )
イデアルに対し、簡約グレブナ基底は一意に定まる
グレブナ基底を求める
Buchbergerのアルゴリズム
入力: イデアルの生成元 F f1 ,, f n
出力: グレブナ基底 G g1 ,, g m
G : F ;
S多項式: ij lcm (HT ( g i ), HT ( g j )) として
ij g i
ij g j
do {
Spol ( g i , g j )
のこと
in ( g i ) in ( g i )
F : G ;
Gの任意のペア(i ,j )に対し、Spol(gi ,gj )を計算;
Spol(gi ,gj )をGの要素で簡約したものをg’ とする;
g’ が0でなければ、Gに加える;
Gの要素で割り、剰余を求めること
} while( F G )
問題点: • ペアの数が膨大になる
• 簡約に時間がかかる
Buchbergerアルゴリズムの
主な改良法
簡約の高速化
計算不要なペアの除去
頭項の比較により、
0に簡約されるペアを一部除く
併用可能
• Buchbergerの規準
• Gebauerの規準
以前の計算結果を用いることで、
0に簡約されるペアを完全に除く
• F5アルゴリズム
あらかじめS多項式を複数生成し、
行列の形式で一度に簡約する
• F4アルゴリズム
トーリックイデアルに
限定したアルゴリズム
行列Aによって定まる多面体の
構造を利用して求める
• non-Buchberger アルゴリズム
今回はF4とF5がターゲット
F4アルゴリズムの概要
複数のS多項式を計算しておく
Symbolic Preprocessing
それらの簡約に必要な元の候補を選ぶ
簡約時に加減算だけで済むよう、単項式倍しておく
Symbolic Preprocessing
入力: 多項式集合F,G
出力: Red = ah | a is monomial , h G
T={F中に出現する全ての項}; Red = { };
while ( HT ( g ) | t なる t T , g G が存在) {
Redに t / HT ( g ) g を追加;
Tからtを除き、t / HT ( g ) g の先頭項以外の項を追加;
}
F4アルゴリズムの概要
S多項式・簡約に使う元を行列で表す
行が多項式、列が単項の種類を表す
簡約 = 行列の対角化 (多項式の定数倍・加減算)
例: 2 x 2 3x 6 y 2 3 y 1, 2 xy x 3 y 2 y 1 を
G 2 x 2 3 y 2, x 2 y 2 1 で簡約
0 3 6 3 1
2 1 3 1 1
(簡約に使った元) 2 0 0 0 3 2
(簡約に使った元) 0 0 1 2 0 1
(簡約される元) 2
(簡約される元) 0
x 2 xy
x
y2
y
1
対角化
2
0
0
0
0 0 0 3 2 (簡約に使った元)
2 0 1 1 0 簡約された結果
0 1 2 0 1 (簡約に使った元)
0 0 0 0
0 0に簡約された
x 2 xy
x
y2
y
1
簡約した結果 2 xy y 2 y
トーリックイデアルに対する
F4アルゴリズム
行列
トーリックイデアル I
0
1
0
1 0 1
0 1 0
0 1 0
A
x u x v | Au Av, u, v N n
各行には1,-1が1個ずつだけ、他は0
1 が -1 より左に来る
行列は非常に疎であり、メモリを浪費する
データ構造とアルゴリズムの改善
行列を有向グラフとして表す
列 0 i1 0 j1 0 を、有向辺 (i, j )とする
行列の変形 = 枝の付け替え
1 0 1 0 1
0 1 0 1
1 1 0 0
3
2
4
1 0 0 1 1
0 1 0 1
0 0 1 1
3
2
出次数が２以上
入・出次数が両方１以上
の場合、辺を付け替える
4
F5アルゴリズムの概要
新たに多項式を生成したとき、生成に使った
多項式の情報を保持しておく
例: 入力を
f1 , f 2 , f3 としたとき、S多項式
f 4 xf2 yf 3 が生成されたとする
このとき f 4 の代わりに r4 ( xF2 , f 4 ) を加える
f 4 は xf2 で生成される、という意味
2
さらに f 5 x f 4 yzf 3 が生成されたとすると、 Ruleとして後で使う
r4 ( xF2 , f 4 ) の情報を用いて r5 ( x 3 F2 , f 5 ) を加える
f 5 は x3 f 2 で生成される、という意味
3
さらに f 6 x f 4 zf 2 が生成されたとすると、
r5 ( x 3 F2 , f 5 ) の情報を用いると、これが 0 に簡約されると分かる
この判定法を用いる
0に簡約されるようなS多項式を、全く生成しない
Buchberger, 改良したF4, F5
のベンチマーク – 実験の環境
入力: 行列 An 1 2 n の
トーリックイデアルの生成元
x
2
1
項順序
x2 , x1 x2 x3 , x1 x3 x4 , , x1 xn1 xn
全次数逆辞書式順序
辞書式順序
変数順序は x1 x2 xn
計算代数システムasir上での実装
３つのアルゴリズムの比較
組み込みのBuchbergerアルゴリズム (modular計算はしない)
今回改良したF4アルゴリズム
F5アルゴリズム
CPU : UltraSPARC-II 360MHz, メモリ : 2GB
ベンチマーク
(n=10～40,全次数逆辞書式順序)
Buchberger
F5
改良したF4
1000
実行時間(s)
100
10
nを増やすと、実行時間は指
数的に増える
実行時間は、
F4 < F5 < Buchberger の順
1
0.1
0.01
10
15
20
25 nの値 30
35
40
45
ベンチマーク
(n=10～40,辞書式順序)
Buchberger
F5
改良したF4
1000
実行時間(s)
100
nが増加するにつれ、改良
したF4は、Buchbergerよりも
性能が悪くなっていく
F5は極端に悪い
10
1
0.1
10
0.01
15
20
25
nの値
30
35
40
F4,F5の計算時間増大の原因
辞書式順序でF4,F5の計算時間が増える理由
生成される多項式の次数(sugar)が増大
A20の場合、基底の最大次数は
全次数逆辞書式の場合 ･･･ 3
辞書式の場合 ･･･ 20
F4の場合、簡約行列のサイズが冗長になる?
F5の場合、不要なペア・Ruleの数が増大?
A20を例に実験を行った結果･･･次ページ
F4による
A20のグレブナ基底計算の効率
全次数逆辞書式順序 ･･･
sugar
S多項式の数
簡約に使う
多項式の数
0以外に簡約された
S多項式の数
3
4
171
2109
17
373
171
0 （終了）
辞書式順序 ･･･
S多項式
0に簡約されないS多項式
簡約に使う多項式
• sugarが大きくなるにつれ、極少数の
多項式を、多数の多項式で簡約しよう
としている
• それに対し、得られる非零な正規形
はただ１つだけ
2500
多項式の数
行列演算の利点を
生かしている
2000
1500
1000
500
この場合、逆に効率が悪くなる
0
3
5
7
9
11 13 15 17 19 21
sugar
F5 による
A20のグレブナ基底計算の効率
全次数逆辞書式順序 ･･･
次数 ペアの数
S多項式の数
3
171 （終了）
324
•次数４以上の項は生成されない
•生成されたS多項式は、必ず0以外に
簡約される
辞書式順序 ･･･
ペアの数
S多項式の数
1000
• 生成される多項式の次数が大きい
ものが存在
• それにより、次数が大きくなっても
かなりの数のペアが残り、計算に
時間を食う
• ペアの選択が、先頭項のLCMの次数
(Sugarを使わない) によるのも原因
多項式の数
800
600
400
200
0
2
5
8
11 14 17 20 23 26 29 32
ペアの次数
実験結果
組み込み関数とF4,F5の比較
全次数逆辞書式順序では、F4,F5の方が高速
辞書式順序では逆に時間がかかる
今後は
F4の場合、わずかな多項式を得るために必要以上の
計算を行っている
F5の場合、次数が大きくなったときに、ペアの選択
ストラテジーがうまく働かない
F4について、簡約時に生成される行列をより小さく
する
F5について、sugarを使う方式に書き換える
ことが考えられる
ありがとうございました
© Copyright 2024 ExpyDoc
