ブッフベルガーアルゴリズム

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーのアルゴリズム①】 今日知ってるといい知識は次ぶなっ！ グレブナー基底の判定法　togetter.com/li/893456 S多項式で遊ぼう　togetter.com/li/895358 ぶなっ！

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーのアルゴリズム②】 それでは、早速「ブッフベルガーのアルゴリズム」を紹介するぶな！ ここでは、K[x_1,…,x_n]で単項式順序が一つ決められているとするぶなよっ！ 【アルゴリズム】 入力：多項式の集合F={f_1,…,f_s} 出力：<F>のグレブナー基底

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーのアルゴリズム③】 G:=F P:={ {f_i,f_ j} | f_i ≠ f_ j in G} while P≠Ø 　{f_i,f_ j} in P を一つ選ぶ 　P:=P - {f_i,f_ j} 　h:=S(f_i,f_ j) (mod G)

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーアルゴリズム④】 　if(h≠0) 　　P:=P⋃{ {u,h} | u in G} 　　G:=G⋃{h} 　end if end while return G ここで、Øは空集合、- は集合の差、(mod G)はその左の多項式をGで割った余りを意味してるぶな！

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーアルゴリズム⑤】 このアルゴリズムを詳しく見ていくぶなっ！ まず、このアルゴリズムは、有限個の多項式を入力すると、それらで生成されるイデアルのグレブナー基底を計算するものぶなっ！ では、どのように計算するかを具体的な多項式で確かめてみるぶなっ！

グレブナー基底大好きbot @groebner_basis

【アルゴリズム⑥】 実数係数３変数多項式環R[x,y,z]で、辞書式順序x>y>zを考えるぶな！ F={f_1=xy-1, f_2=xz-1} とするぶな！ まず、G:=Fとするぶな。 さらに、P:={{f_1,f_2}} とするぶな。（PはGの多項式のすべてのペアぶな）

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーのアルゴリズム⑦】 ここで、もちろんP≠Øぶなから、 一回目のwhileループに入るぶな。 [一回目のwhile] {f_1,f_2}をPから選び、新たに P:=P-{f_1,f_2}=Ø と置きなおすぶな。 そして、選んだf_1,f_2のS多項式を計算するぶな。

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーのアルゴリズム⑧】 昨日やった「S多項式で遊ぼう」の計算結果から、 S(f_1,f_2)=y-z となり、これをGで割った余りも、y-zになるぶな。 よって、h:=y-zとするぶな。

グレブナー基底大好きbot @groebner_basis

【アルゴリズム⑨】 ここで、h≠0ぶなから、ifの条件を満たすぶな。よって、 PにhとGの多項式とのペアを加え、 P:=P⋃{ {f_1,h}, {f_2,h} }=Ø⋃{ {f_1,h}, {f_2,h} }={ {xy-1,y-z}, {xz-1,y-z} } とするぶな。

グレブナー基底大好きbot @groebner_basis

【アルゴリズム⑩】 そして、Gにhを加え、 G:=G⋃{h}={xy-1,xz-1.y-z} として、一回目のwhileループを終わりにするぶな。 ここで、P={ {xy-1,y-z}, {xz-1,y-z} }≠Ø ぶなから、二回目のwhileループに入るぶな。

グレブナー基底大好きbot @groebner_basis

【⑪】 [二回目のwhile] {xy-1,y-z}を選び、P:=P- {xy-1,y-z}={ {xz-1,y-z} }とするぶな。 xy-1とy-zのS多項式を計算するぶな。 S(xy-1,y-z)=xz-1 で、これはG={xy-1,xz-1,y-z}で割ると0になるぶな。

グレブナー基底大好きbot @groebner_basis

【アルゴリズム⑫】 したがって、h=0となるぶな。これは if の条件を満たさないぶなから、そのまま二回目のwhileループを終わるぶな。 ここで、P={ {xz-1,y-z} }≠Ø ぶなから、３回目のwhileループに入るぶな。

グレブナー基底大好きbot @groebner_basis

【⑬】 [三回目のwhile] Pから{xz-1,y-z}を選び、P:=P- {xz-1,y-z}=Øとするぶな。 xz-1とy-zのS多項式を計算するぶな。昨日の計算から、 S(xy-1,y-z)=xz^2-y で、これはG={xy-1,xz-1,y-z}で割ると0になるぶな。

グレブナー基底大好きbot @groebner_basis

【アルゴリズム⑭】 したがって、今度もh=0となるぶな。これは if の条件を満たさないぶなから、そのまま三回目のwhileループを終わるぶな。 ここで、P≠Ø ぶなから、whileループに入らず、このときのGを返してプログラムを終わりにするぶな。

グレブナー基底大好きbot @groebner_basis

【⑮】 最終的に、出力されるGはG={xy-1,xz-1.y-z}になっているぶな。これは、昨日確認したように、確かに<xy-1,xz-1>のグレブナー基底ぶなねっ！ このようにブッフベルガーアルゴリズムは、多項式を入力すると、そのグレブナー基底を計算してくれるぶな！

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーアルゴリズム⑯】 でも、本当に任意の多項式について、グレブナー基底を出力してくれるか気になるぶなね！ 次回は、このアルゴリズムの、正しくグレブナー基底を出力すること「正当性」と、無限ループに入らず必ず終わること「停止性」を数学的に証明するぶなよっ！

グレブナー基底大好きbot @groebner_basis

【今日のまとめ】 「ブッフベルガーアルゴリズムは、グレブナー基底を計算してくれる」 ぶなっ！

グレブナー基底大好きbot @groebner_basis

今日の参考文献も、「グレブナ基底と代数多様体入門」ぶなよ！togetter.com/li/877168