PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

あいねぜんじゅう
4 years ago
Views:

1 計算代数幾何学入門 - グレブナー基底とその応用 - 工藤桃成 * * 九州大学大学院数理学府数理学専攻九大整数論セミナー 2017/6/8( 木 ) 6/5/2017 1

2 目次 : 1. Introduction 2. Gröbner bases 3. Applications 4. How do we study Computational Algebraic Geometry? 6/5/2017 2

3 Computational/Computer Algebra 計算代数 (Computational Algebra) は, 代数学の問題を解くアルゴリズムに関する研究を行う分野のこと. 代数学の応用領域である暗号符号分野におけるアルゴリズムの研究を含む場合もある. cf. 計算機代数 (Computer Algebra) は, 計算代数のアルゴリズムを計算機上で利用する際に生じる課題及びそれに付随する課題に関する研究を行う分野のこと. 参考 : 日本数式処理学会 HP [1] 長坂耕作, 数式処理と計算機代数の不思議, 数式処理 Bulletin of JSSAC, 22 (2), pp. 1-2, /5/2017 3

4 Studies with mathematical software 都市計画 ( 社会インフラ開発 ) AI 機械学習ビッグデータ解析計算 ( 機 ) 代数で扱う問題情報セキュリティ ( 暗号符号 ) 画像処理など最適化幾何学実社会の産業技術統計解析数学応用数学応用解析 ( 微分方程式 ) 災害予測シミュレーション代数学 ( 含 : 整数論代数幾何学 ) 確率論数理ファイナンス金融保険 6/5/2017 4

5 Computational Algebraic Geometry 計算代数幾何学 (Computational Algebraic Geometry, CAG for short) は, 主に代数幾何学の問題を解くためのアルゴリズムに関する研究を行う分野のこと CAG におけるアルゴリズム : - 連立代数方程式の求解 - Gröbner 基底 - Sheaf cohomology と関連する不変量 - 特殊な代数多様体の数え上げ etc. 6/5/2017 5

6 The purpose of this talk 本講演では, CAG において基本的な道具である Gröbner 基底と, その応用について概説します. また, 講演者が海外における数学ソフト開発の現場を訪れて学んだこと ( アルゴリズムの設計や, 計算機を活用する数学研究など ) を紹介します. 6/5/2017 6

7 目次 : 1. Introduction 2. Gröbner bases 3. Applications 4. How do we study Computational Algebraic Geometry? 6/5/2017 7

8 Gröbner bases K[x 1,, x n ] : 体 K 上の n 変数多項式環 I : 多項式環 K[x 1,, x n ] のイデアルイデアル I の Gröbner 基底 : I のよい生成元集合のこと 6/5/2017 8

9 Applications of Gröbner bases 多変数代数方程式系 ( 高次の連立代数方程式 ) の求解 - 暗号解読など, 様々な分野への応用可能性可換環のイデアルに限らず, 抽象代数における様々な対象の計算代数多様体の非特異性判定連接層のコホモロジー群の計算線形計画整数計画 ( 最適化 ) 実験計画 ( 統計 ) etc. 6/6/2017 9

10 A motivation of Gröbner bases f K[x 1,, x n ], I = g 1,, g s : 多項式 g 1,, g s で生成されるイデアル Problem: 与えられた f と g 1,, g s に対して, f I か否か判定せよ Solution?: 後述のアルゴリズムによって, f = h 1 g h s g s + r と表すここで h 1,, h s, r K[x 1,, x n ] もし r = 0 なら f I. でも r 0 なら f I か? 6/5/

11 The case of K[t] K[t] : 体 K 上の 1 変数多項式環 I = g(t) : 多項式環 K[t] のイデアル (1 変数の場合イデアルは単項生成 ) Problem: 与えられた g に対して, f I か否か判定せよ Solution: 割り算アルゴリズムによって f = hg + r (! h,! r K[t]) r = 0 なら f I r 0 なら f I 6/5/

12 Characterization of Gröbner bases f K[x 1,, x n ], I : 多項式環 K[x 1,, x n ] のイデアルイデアル I の Gröbner 基底 {g 1,, g s } は, 後述のアルゴリズムによって f = h 1 g h s g s + r と表したときに, 余り r が f と I によって一意に定まるような生成系として特徴付けられるある種の一般化 1 変数多項式環の割り算多変数多項式環の割り算 6/5/

13 ベクトル α 1,, α n (Z 0 ) n を α, Notation 単項式 x 1 α 1 x n α n を x α, 多項式環 K[x 1,, x n ] を K x などと書く注 : 本講演では, 単項式といえば係数 1 のもの 6/5/

14 Monomial orders M n {x α α Z 0 n } : 多項式環 K x の単項式全体の集合 Def. M n の順序が次の (1)-(3) を満たすとき, 単項式順序 (Monomial Order) という : (1) は全順序 (2) は整列順序 (3) s, t M n with s t ならば, u M n, su tu 6/5/

15 Lexicographic order x α lex x β i such that def α 1 = β 1,, α i 1 = β i 1, and α i > β i e.g. n = 3, x 2 y 4 z 3 lex x 2 y 3 z 5 Exponent : (2,4,3) (2,3,5) 左から順に勝ち負けを判定 lex は単項式順序であり, 辞書式順序 (lexicographic order) と呼ばれる 6/5/

16 Graded reverse lexicographic order x α grevlex x β α > β, または def α = β かつ i such that e.g. n = 3, x 3 y 4 z 3 grevlex x 2 y 5 z 3 Total degree : Exponent : (3,4,3) (2,5,3) α n = β n,, α i+1 = β i+1, and α i < β i grevlex は単項式順序であり, 次数付き逆辞書式順序 (graded reverse lexicographic order) と呼ばれるまず総次数で判定. 決着がつかないなら右から勝ち負けを判定 6/5/

17 A remark for efficient computation Gröbner 基底の計算では, 次数付き逆辞書式順序が比較的速いとされる計算代数システムで Gröbner 基底の計算が終わらない実装されている関数の単項式順序を check!!! 次数付き逆辞書式順序に変更して計算せよもし辞書式順序に関する Gröbner 基底が欲しければ, 入力生成系順序を変更して計算次数付き逆辞書式順序に関する GB Gröbner 基底変換 (FGLM 変換など ) 辞書式順序に関する GB 6/5/

18 Leading monomials, terms, coefficients M n = x α α (Z 0 ) n の単項式順序を fix する. 各 f = α Z 0 n c α x α K x {0} に対して, mltdeg f max {α Z n 0 : c α 0} f の多重次数 (multi degree) LM f x mltdeg(f) 先頭単項式 (Leading Monomial) LC f c mltdeg(f) 先頭係数 (Leading Coefficient) LT f LC f LM f 先頭項 (Leading Term) 6/5/

19 lex with x y Examples of LM, LT and LC f = 2x 3 y + x 2 y 2 4x 5 y 2 + 3y 3 x + 5 Q[x, y] multdeg f = (5,2), LM f = x 5 y 2, LC f = 4, LT f = 4x 5 y 2 f の多重次数 (multi degree) 先頭単項式 (Leading Monomial) 先頭係数 (Leading Coefficient) 先頭項 (Leading Term) 6/5/

20 Division in multivariate cases Prop. G = {g 1,, g s } K x {0} このとき, f K x, h 1,, h s, r K x such that f = h 1 g h s g s + r r に現れるどの単項式も LT (g i ) (1 i s) のいずれでも割り切れない mltdeg f mltdeg (h i g i ) if h i 0 for 1 i s r を f,g と書き, f をに関して G で割った余りと呼ぶ Rem. f g 1,, g s r g 1,, g s 6/5/

21 Pseudocode for division algorithm Input : f, g 1,, g s s Output : h 1,, h s and r such that f = i=1 h i g i + r h i 0; r f while i such that LT (r) is divisible by LT (g i ) do end while Choose i such that LT (r) is divisible by LT (g i ) r r LT r LT g i g i ; h i h i + LT (r) LT (g i ) g i return h 1,, h s and r 6/5/

22 r = 0 ならば f I か? Yes. f I ならば r = 0 か? 一般には No. Gröbner bases e.g. K[x, y, z], lex において f = x y2 z z 1 は G = {x 2 + z 2 1, x 2 + y 2 + z 1 2 4} の生成するイデアル I = G の元だが, f,g = 1 2 y2 z z z 2 0 6/5/

23 How do we define Gröbner bases? 前頁の例において, f = x y2 z z 1 は G = {g 1 x 2 + z 2 1, g 2 x 2 + y 2 + z 1 2 4} の生成するイデアル I = G の元だが, f,g = 1 2 y2 z z z 2 0 であり, f,g I の先頭項 1 2 y2 z を割り切る LT (g i ) は存在しない f,g = 0 for f I が成り立つためには, 全ての f I について LT (f) がある LT (g i ) で割り切る必要がある ( 実はこれが必要十分条件 ) 6/6/

24 Definition of Gröbner bases Def. : 単項式順序, g 1,, g s K x {0} G = {g 1,, g s } がイデアル I K x のに関する Gröbner 基底 f I {0}, i such that LT (f) は LT (g i ) で割り切れる f I {0}, f,g = 0 Rem. I の Gröbner 基底は I を生成する 6/5/

25 Uniqueness of a remainder Prop. イデアル I K x のに関する Gröbner 基底 G について次が成立 : f K x が, f = g + r = g + r, g, g I, r, r K x, LT (h) が r, r に現れるいずれかの項を割り切るような h G は存在しないの2 条件を満たすならば, r = r 単項式順序に関する Gröbner 基底 G に対し, 余り f,g は一意に決まるこれを NF,G (f) と書き, と G に関する f の正規形 (normal form) という 6/6/

26 S-polynomials Def. 多項式 f, g K x {0} に対して, S f, g LCM LM f, LM g LT f f LCM LM f, LM g LT g を f と g のに関する S 多項式 (S-polynomial) という g e.g. lex, f: = x 3 y 2x 2 y 2 + x, g: = 3x 4 y LT f = x 3 y, LT g = 3x 4, LCM LM f, LM g = x 4 y S f, g = x4 y x 3 y f x4 y 3x 4 g = xf 1 3 y g = 2x3 y 2 + x y2 6/5/

27 Buchberger s criterion Thm. (Buchberger, [2]) : 単項式順序, g 1,, g s K x {0} G = {g 1,, g s } がイデアル I = G K x のに関する Gröbner 基底 S g i, g j,g = 0 for i, j with gi g j 各ペア (g i, g j ) with g i g j ごとに r i,j S g i, g j,g I を計算し, r i,j 0 ならば r i,j を G に付け加えるという操作を繰り返すことで, Gröbner 基底を計算するアルゴリズムを得る [2] B. Buchberger, An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal, Ph. D. dissertation, University of Innsbruck, /5/

28 Pseudocode for Buchberger s algorithm Input : f 1,, f s ; Output : Gröbner basis G = {g 1,, g s } for I = f 1,, f s G {f 1,, f s }; B { {g 1, g 2 } g 1, g 2 G with g 1 g 2 } while B do select {g 1, g 2 } from B B B {{g 1, g 2 }}; r S (g 1, g 2 ); r 0 r,g if r 0 0 then B B { {g, r o } g G} ; G G {r 0 } end if end while return G 6/5/

29 Properties of Gröbner bases 前項の Buchberger アルゴリズムは有限回のステップで停止するイデアルの Gröbner 基底 G で, p, q G に対して, p に現れるいずれの単項式も LT (q) で割りきれないものを被約 Gröbner 基底という全ての多項式の先頭係数が 1 である被約 Gröbner 基底をモニックな Gröbner 基底という単項式順序とイデアル I に対して, モニックで被約な Gröbner 基底は一意に存在する 6/6/

30 Gröbner bases algorithms 計算代数システムにおける実装状況 : MAGMA, Maple, SageMath, SINIGULER, Macaulay2, Mathematica, etc. F4/F5 algorithms by Faugére [3], [4] - 線形代数における Gaussian elimination の一般化実装 : Maple, MAGMA (Faugére 自身の実装と collaborate) [3] J.-C. Faugére, A new efficient algorithm for computing Gröbner bases (F4), J. of Pure and Applied Mathematics, Elsevier Science, 139 (1), pp , [4] J.-C. Faugére, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), In: Proc. of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC), ACM Press, pp , /7/

31 目次 : 1. Introduction 2. Gröbner Bases 3. Applications 4. How do we study Computational Algebraic Geometry? 6/5/

32 Applications of Gröbner bases 多変数代数方程式系 ( 高次の連立代数方程式 ) の求解 - 暗号解読など, 様々な分野への応用可能性可換環のイデアルに限らず, 抽象代数における様々な対象の計算代数多様体の非特異性判定連接層のコホモロジー群の計算線形計画整数計画 ( 最適化 ) 実験計画 ( 統計 ) etc. 6/6/

33 Solving multivariate systems Prob. 与えられた f 1,, f s K[x 1,, x n ] に対して, f 1 a 1,, a n = = f s a 1,, a n = 0 を満たす a 1,, a n K n を全て求めよ, i.e. I f 1,, f s に対して, V I : = a 1,, a n K n f a 1,, a n = 0, f I を決定せよ Gröbner 基底を使って代数的に解くことを考える 6/5/

34 Elimination Theorem Thm. ( 消去定理 ) lex : 辞書式順序 with x 1 x n G : イデアル I の lex に関する Gröbner 基底このとき, 1 l n に対して G K[x l,, x n ] はイデアル I K[x l,, x n ] の Gröbner 基底である ( 単項式順序は lex の x l,, x n への制限を使用 ) Rem. a 1,, a n V(I) a l,, a n V(I K[x l,, x n ]) 6/5/

35 An idea for solving multivariate systems 与えられた f 1,, f s に対して, 1. イデアル I = f 1,, f s の lex に関する Gröbner 基底 G を計算 2. G K[x n ] の元の根 a n V(I K[x n ]) を求める 3. G K[x n ] の元の各根 a n を G K[x n 1, x n ] の元に代入し, a n 1, a n V(I K[x n 1, x n ]) なる a n 1 K を求める. Rem. a n 1, a n V(I K[x n 1, x n ]) なる a n 1 が存在するとは限らない 6/6/

36 Example of solving a multivariate system f 1 x 2 + y 2 + z 2 4, f 2 x 2 + 2y 2 5, f 3 xz 1 x y z なる lex に関して f 1, f 2, f 3 の ( モニックな ) Gröbner 基底を求めると, G = {x + 2z 3 3z, y 2 z 2 1, z z2 + 1 } 2 g 3 z z2 + 1 の根を求める 2 g 3 の各根を g 1 x + 2z 3 3z と g 2 y 2 z 2 1 の z に代入し, V f 1, f 2, f 3 = V g 1, g 2, g 3 を求めることができる 6/6/

37 Applications of Gröbner bases 多変数代数方程式系 ( 高次の連立代数方程式 ) の求解 - 暗号解読など, 様々な分野への応用可能性可換環のイデアルに限らず, 抽象代数における様々な対象の計算代数多様体の非特異性判定連接層のコホモロジー群の計算線形計画整数計画 ( 最適化 ) 実験計画 ( 統計 ) etc. 6/6/

38 Extension to other algebraic objects Gröbner 基底の理論は R = K x のみならず t R = j=1 K x : 有限ランク自由加群 R = K x 1,, x n x1,,x n : 局所化 R = K[ x 1,, x n ] : べき級数環 R = K{x 1,, x n } : 収束べき級数環 R = K n : 外積代数などにおいても展開される 6/6/

39 Extension to free modules K x 上の有限ランク自由加群の場合 K x t j=1 K x 単項式 x α x α e i = (0,, 0, x α, 0,, 0) 単項式順序 lex, grevlex, etc. > TOP,lex, > POT,lex, etc. イデアル I = f 1,, f s 部分加群 N = f 1,, f s 6/5/

40 Term-Over-Position (TOP) order : K x における単項式順序 x α e i > TOP x β e j x α x β または def x α = x β かつ i < j e.g. n = 3, R = K x, y, z 2 x 2 y 3 z 5 e 1 > TOP,lex x 2 y 3 z 5 e 2 まず K x の単項式順序で判定決着がつかないなら e i の順序で勝ち負けを判定 > TOP はに関する Term-Over-Position (TOP) 順序と呼ばれる 6/6/

41 Computing several objects in algebra t S = K x 上の自由加群 j=1 シジジー加群有限生成加群の自由分解 ( 射影分解 ) Ext 加群, Tor 加群 S における Gröbner 基底の理論を用いることで, などを計算することができ, これを用いることでさらに, 代数幾何学における連接層のコホモロジー群なども計算できる詳細は [5] などを参照 [5] D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, GTM 150, Springer, /5/

42 Books about Gröbner bases Gröbner 基底に関連する書籍を幾つか挙げる [6] W. W. Adams and P. Loustaunau, An introduction to Gröbner Bases, AMS, Graduate Studies in Mathematics, 3, [7] T. Becker and V. Weispfenning, Gröbner Bases - A Computational Approach to Commutative Algebra, GTM 141, Springer-Verlag, New York, [8] D. Cox, J. Little and D. O shea, Using Algebraic Geometry, GTM 185, Springer-Verlag, New York Berlin, [9] 丸山正樹, グレブナー基底とその応用, 共立出版, [10] D. Cox, J. Little and D. O shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4th edition, Springer-Verlag, New York, なお, 本講演で登場した計算例については [8] を参考にした 6/7/

., White-Box, White-Box. White-Box.,, White-Box., Maple [11], 2. 1, QE, QE, 1 Redlog [7], QEPCAD [9], SyNRAC [8] 3 QE., 2 Brown White-Box. 3 White-Box

., White-Box, White-Box. White-Box.,, White-Box., Maple [11], 2. 1, QE, QE, 1 Redlog [7], QEPCAD [9], SyNRAC [8] 3 QE., 2 Brown White-Box. 3 White-Box White-Box Takayuki Kunihiro Graduate School of Pure and Applied Sciences, University of Tsukuba Hidenao Iwane ( ) / Fujitsu Laboratories Ltd. / National Institute of Informatics. Yumi Wada Graduate School