0. Introduction (Computer Algebra) Z, Q ( ), 1960, LISP, ( ) ( ) 2

Size: px

Start display at page:

Download "0. Introduction (Computer Algebra) Z, Q ( ), 1960, LISP, ( ) ( ) 2"

みりあいさし
5 years ago
Views:

1 ( ) 1

2 0. Introduction (Computer Algebra) Z, Q ( ), 1960, LISP, ( ) ( ) 2

3 ,, 32bit ( 0 n n , mod2 32 ) 64 bit Z (bignum; GNU gmp ) n Z n = ±(b l 1 B l b 0 B 0 ) (B = 2 32, 0 b i ) q Q, Z ( ) 3

4 , garbage collection f Q[x] linked list f Q[x 1,..., x n ] linked list, linked list linked list,,, garbage collector 4

5 , : : or No, ( : GCD) 5

6 ,, 1. GCD,, ( ) 6

7 Knuth, The Art of Computer Programming Vol 2, Addison Wesley,, Rokko Lectures in Math (pdf web ),,, Cox, Little, O Shea, Ideals, Varieties and Algorithms, Springer UTM, Using Algebraic Geometry, Springer GTM,,, (Singular, CoCoA, Macaulay ) 7

8 ,, MAXIMA : (Macsyma ) AXIOM :, ( ) Macaulay2, Singular, CoCoA :, PARI/GP : Risa/Asir :, Kan/sm1 : Knoppix/Math 8

9 Knoppix/Math CD/DVD Linux (Live Linux) ( ) debian (Linux distribution ),, ICM 2006, Windows PC CD/DVD Windows HDD USB (Windows ) VMWare 9

10 VMware Player Windows VMare Knoppix/Math 1 : DVD Windows, 2 : Knoppix/Math Windows, Windows, HDD Knoppix/Math ( 512MB ) 10

11 1. GCD K :, R = K[x] R PID, I R f I I = f., R., fg R g 0, q, r R f = qg + r, deg(r) < deg(g) (r = remainder(f, g)). 11

12 f, g K[x] while g 0 do r remainder(f, g); f g; g r end while return f K. K = Q, K = Q(y) subresultant GCD modular GCD 12

13 Subresultant GCD ( ; pseudo-remainder) R UFD (R[x] GCD ) f, g R[x], g 0, deg(f) deg(g) prem(f, g) = remainder(lc(g) deg(f) deg(g)+1 f, g) (lc(g) g ; prem(f, g) R[x]) remainder prem, Q(R),, prem R 13

14 Subresultant f 1 f, f 2 g, g 1 1, h 1 1, j 1, n j = deg(f j ), e j = n j n j+1 do (1) f j+2 prem(f j, f j+1 )/(g j h e j j ) g j+1 lc(f j+1 ) (2) h j+1 h 1 e j j g e j j+1 if f j+2 = 0 return f j+1 end do 14

15 Subresultant 1. e j = 1 n j 1, f j+2 = prem(f j, f j+1 )/lc(f j ) 2 2. (1), (2) f j, h j, f, g S (Sylvester ) minor 3. GCD(f, g) = 1 f j = ± det(s) 4. GCD(f, g) = 1 (modular GCD) ( ) 15

16 2. ( ) 1. Fp Berlekamp, Cantor-Zassenhaus 2. Q Fp Hensel lifting, Z 3. f, g K(α) 4. K(α) K 16

17 3. Introduction K n R = K[X] = K[x 1,..., x n ] (GB), R I. f I ( ) I V (I) I ( ), I J, I : J, I : J I (I = Q i, Q i : ; I = P i, P i : ). I Hilbert H I (s) 17

18 ( ) 1. :,, 2., Hilbert 3. R/I, support,,,, saturation,, 18

19 4. (S- ) R = K[X], f, g R, Spoly(f, g) = t HM(f) f t = LCM(HT(f), HT(g)) t HM(g) g, Spoly(f, g), f, g,. (Buchberger) G I = G (GB) g 1, g 2 G, Spoly(g 1, g 2 ) G 0 : 19

20 Buchberger ( ) : F = {f 1,, f l } : F G D {{f, g} f, g F ; f g}; G F while ( D ) do C = {f, g} D ; D D \ {C} h NF G (Spoly(f, g)) if h 0 then D D {{f, h} f G}; G G {h} end while return G 20

21 Buchberger, Dickson (Hilbert ) G,. D 0 S. 21

22 , G I. f, g G, HT(f) HT(g) G \ {g} I GB (by ). GB F f, NF F \{f} (f) GB G I GB., HC(g) = 1 GB GB identify 22

23 Buchberger., (graded) ( : ), : ( 0 S-, S-, etc.)., Risa/Asir,. 23

24 1) trace p F f p HC(f). φ : Z Z/ p = Fp. Buchberger trace (Traverso) φ(g) φ(f ) GB, G F failure. 24

25 trace : GB D {{f, g} f, g F ; f g}; G F while ( D ) do C = {f, g} D ; D D \ {C} if NF φ(g) (Spoly(φ(f), φ(g))) 0 then h NF G (Spoly(f, g)) (, ) if h 0 p HC(h) then D D {{f, h} f G}; G G {h} else return failure endif endif end while return G 25

26 trace : HT(φ(g)) = HT(g) ( g G) φ(nf G (f, g)) = NF φ(g) (φ(f), φ(g))) ( f, g G), φ(g) φ(f ) GB G F. 1. G G GB? G Buchberger 2. F G? G GB NF G (f) = 0 (f F ) 26

27 2) trace trace : Z ( NF Z ),, +trace ( ) 27

28 trace (in Risa/Asir) 1. F h F : f h = h d f(x 1 /h,..., x n /h) 2. G h F h trace check 3. G G h h=1, G F. F,,. 4. G G F GB. step

29 trace, ( ) trace vs non-trace f ilter9, f abrice24 trace vs trace jcf 26, assur44, f abrice24 29

30 3) S d := d S- G d := d S d F G d = GB, d ( d + 1 ), G d, G d S 0 Q,, content 30

31 (in Risa/Asir, CoCoA) d, OK Risa/Asir 6 1, 31

32 4) F 4 (J.C. Faugère) while D do S S ; D D \ S R NF Gd 1 (S) reducers ({tg g G d 1 }) T Span(S R), R D {(g, h) h T }; G G T end while 32

33 F 4 S S R : symbolic preprocessing 1. S. 2. h, h = tht(g) g G, T (t(g HM(g))), tg R 33

34 Span(S R) F 4 = Span(S R) (rref) CRT, Hensel CRT A rref 1. A mod p i Fp i I M i O O 2. M M i mod p i M CRT 3. - M M mod p i 4. A ( I M ) 34

35 F 4 A reducer, CRT reducer CRT, 0, Faugère (1999),, 35

36 5) F 4 Buchberger (in Risa/Asir) F 4 Buchberger hybrid without trace NF Gd 1 (S d ) ( Buchberger), ( F 4 ) reducer set R, Q 0 36

37 F 4 Buchberger (in Risa/Asir) F 4 Buchberger hybrid +trace with trace S d F p F 4, S d (F 4 trace) S d, Q Q 0 GB, trace 37

38 F 4 F 4 (+trace) ( trace, ) 2 ( cyclicn ) Magma (by A. Steel) CRT, (?) SALSA or Maple11 (by Faugère) (?),, ( )? 38

39 6) Modular change of ordering Change of ordering ( ) GB, ( ) GB. FGLM, Hilbert driven algorithm, Groebner walk. Modular Change of ordering FGLM modular, 39

40 Change of ordering : FGLM I : 0 (dim K K[X]/I < ) G 0 : < 0 I GB G ; B {1}; H do N (x 1 B x n B) \ H if N = return G else h min < N if T (f) (B {h}) f I then G G {f}; H H {h} else B B {h} end do 40

41 FGLM T (f) (B {h}) f I incremental : 1. NF G0 (h 0 ),..., NF G0 (h i 1 ) 2. NF G0 (h i ) 0, f 3. 0 H, (modular change of ordering) 41

42 Compatibility R :, K :, φ : R K : P = Ker(φ) :, φ : R P F R[X], F Q(R)[X]. 1. φ (F, <) permissible φ(hc(f)) 0 ( f F ) ( ) 2. φ F compatible φ(f ) = φ( F R[X]) φ(f ) φ( F R[X])!! 42

43 Compatibility, GB G F R[X] F < GB. φ (G, <) permissible φ(g) φ(f ) 1. φ(g) φ(f ) GB. 2. φ F compatible. 43

44 Compatible GB G F R[X] F, < (φ, F )- compatible GB φ (G, <) permissible φ(g) φ(f ) GB. R PID 1. φ F compatible, 2. G I = F (φ, F )-compatible GB G I GB. 44

45 Modular change of ordering ( ) F < Q GB (F Z[X]) G 0 F < 0 GB do p (G 0, < 0 ) permissible G G 0 (φ, G 0 )-compatible GB G return G end do GB G Buchberger or F 4 +trace ( ) +modular (modular FGLM; 0 ) 45

46 GB G φ(g 0 ) < 0 GB, G for each h G do a t t T (h) H t T (h) a t NF <0,G 0 (t) (a HT< (h) = 1) C H X (a t ) if {f = 0 f C} S h = {a t = c t } then G G { t T (h) else return failure end do return G c t t} 46

47 1. F R[X] φ F compatible. 2. G = {g 1,..., g s } (HT(g 1 ) < < HT(g t )) φ(f ) GB. 3. H = {h 1,..., h t } (HT(h 1 ) < < HT(h s )) I GB. 4. g i I R P [X] φ(g i ) = g i (i = 1,..., s, s s) g i = h i (i = 1,..., s ). 47

48 : modular template GB. m f (t) F p f m f (f) I, φ(m f ) = m f, permissible m f (t), m f (t) f 48

49 Risa/Asir GB dp ptod(), dp dtop(), dp ht(), dp hc(), dp rest() non-trace GB nd gr(), nd f4() trace GB nd gr trace(), nd f4 trace() modular change of ordering tolex(), tolex gsl(), minipoly() primedec(), primadec() 49

50 nd gr(), nd f4() nd gr(p oly,v,char,order) trace, Q, Fp, Q(t 1,..., t m ) GB P oly = [f 1, f 2,..., f k ], f i : V V = [x 1, x 2,..., x n ] : Char : 0 Q, p Fp Order = 0 ( ), = 1, ( ), = 2 ( ), [[O 1, N 1 ], [O 2, N 2 ],...] ( ; O i 0, 1, 2, N i ) nd f4(p oly,v,char,order) Q(t) 50

51 nd gr trace(), nd f4 trace() nd gr trace(p oly,v,homo,char,order) Q, Q(t) Buchberger trace Homo : 1, trace, 0 trace Char : 1 1 ( ) p (p : ) Fp. 0 (modular change of ordering ) nd f4 trace(p oly,v,homo,char,order) Q F 4 Buchberger 51

52 minipoly() (in lib/gr) load("gr"); minipoly(g,v,order,f,t ) F Q[X]/ G m(t ). G Order, 0 G GB T / V T GB, 52

53 tolex() (in lib/gr) load("gr"); tolex(g,v,order,w ) G W GB G Order, 0 G GB eco9 (shape base ) G = {x 1 f 1 (x 9 ),..., x 8 f 8 (x 9 ), f 9 (x 9 )} (0 ) 53

54 primedec(), primadec() (in lib/primdec) load("primdec"); primedec(b,v ) Q : [P 1,..., P l ] P i, P i B = i P i primadec(p,v ) Q : [[Q 1, P 1 ],..., [Q l, P l ]] P i, Q i, Q i P i = Q i, B = i Q i 54

. UNIX, Linux, KNOPPIX. C,.,., ( 1 ) p. 2

2009 ( 1 ) 2009 ( 1 ) p. 1 . UNIX, Linux, KNOPPIX. C,.,.,. 2009 ( 1 ) p. 2 , +, ( ), ( ), or PC orange2, knxm2008vm, iyokan-6 KNOPPIX/Math (DVD ) 2009 ( 1 ) p. 3 ,. Mathematica (20-30 /1 ), Maple (20 /1