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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ありがとうございました