ppt file

トーリックイデアルの
グレブナ基底を求める
アルゴリズム – 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 xn1  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を使う方式に書き換える
ことが考えられる
ありがとうございました

Download Report