Gröbner Basis and Applications – A Survey
Contents
1. Math 1 150 166 167 180 WT Wu Wen Ts n 1987 A Zero Structure Theorem for Polynomial Equation Solving Math Mechanization Research Preprints 1 2 12 Academica Sinica Beijing 342. fay 0 S fi f3 a 2xy 2 2 2ry in F Hence we must add f4 2zxy to our generating set and we rename F as F f1 fo fs fa Then Shih SB 0 Sif fa ve 2ey 1 2 a2 2ey 2xy yf so Se Saf oy 2y 2 y a 2y z We have in 2y 2 2y This is not contained in the ideal in F x x y x ry generated by the leading monomials of the elements of F Thus we must also add fs 2y x to our generating set We check 14 S fi fs y 2 2xy 1 22 2y 2ay 1 2 a so Sth fs 0 Similarly all the other EICH fi 0 so that G fi fo f3 fa fs x z 274 Y 2y HT 8 22Y 2y H x is a Gr bner basis for I 5 4 Buchberger s Algorithm The procedure we used in the previous example of adjoining S f F to F if it is nonzero can be elaborated into an algorithm for producing Gr bner bases The Buchberger s Algorithm gives us a method how to construct such a basis in a finite number of operations The version we will present is a very rudimentary one The general idea is to try to extend the original generating set to a Gr bner basis by adding more polynomials in J Theorem 5 Algorithm 2 Buchberger s Algorithm input F fi 4 05 fn output G g1 gs Gr bner basis for I with F CG G F repeat G G for each pair p q p qinG do G 5 S p q if S 0 then G G
3. 2 The S polynomial of f and g is at x HON ane S f g g 11 Example 1 Let f y 2 y z and g 3x y y in R z y with gradlex order Then y 4 2 and 4 2 4 2 S f g Baf hI ry 4 4 ly Properties see CLO 1 An S polynomial S f g is designed to produce cancellation of leading terms 2 We have S f g f g and S f g S af bg for every f g in k z1 n and every a b k 3 For every f g in k z1 n for every a 8 in N there exists 7 in IN such that S x f x g 7 S f g where lem x lm f 2 Im g lcm Im f Im g Y 4 Let p1 Pm k z1 2n with multideg p a a 23 for all i If for some set of c k multideg 5 cipi lt a then 5 Cipi i 1l m veln is some linear combination with coefficient in k of S polynomials Using the S polynomials we have got an other characterization of Gr bner bases which is from an algorithmic point of view better than the definition Theorem 4 Let I be a polynomial ideal Then a basis G g1 9s for Iis a Gr bner basis for I if and only if for all pairs j j the remainder of the division of S gi g by G listed in some order is zero Proof see also CLO Let G is a Gr bner basis Since 9 9 I by proposition 4 the remainder is zero 12 Let f I f 0 We must show that if the S polynomials all give remainders of
4. adjoin further elements to the end of the ordered generating set G Thus there is no reason to recompute those remainders on subsequent passes throught the main loop It is possible to ameliorate this algorithm by using the following results and limitate the efforts of cal culation in the reduction algorithm by ordering the polynomials f fn such that the leading terms grow it will diminuate the number of necessary tests for finding a f such that in f divides in q and in the Buchberger s algorithm by considering at first the pairs p q such that lem in p in q G is as small as possible The probability that S p q 0 will be greater Thus we will faster add elements in the basis which we want to construct and the followings S polynomial reductions will have more chance to be nil Lemma 2 see also CLO Let G be a Gr bner basis for a polynomial ideal I Let p in G be a polynomial such that in p in G p Then G p is also a Gr bner basis for Ie 16 Definition 6 A reduced Gr bner basis for a polynomial ideal I is a Gr bner basis G for I such that 1 lc p 1 for allp in G 2 for every p in G no monomial of p lies in in G p Proposition 6 see also CLO Let I be a polynomial ideal other than 0 Then for a given monomial ordering I has an unique reduced Gr bner bases Example Let the Gr bner basis to the ideal J studied in example 2 in the section 5 3 The Gr bner ba
5. appear La3 Lazard D 1990 A new method for solving algebraic systems of positive dimension Technical Report LITP 89 77 To appear in Discr App Math LRR Z Ligatsikas R Rioboo amp M F Roy 1993 Generic Computation of the Real Closure of an Ordered Field in Symbolic Computation New Trends and Developments International IMACS Symposium SC 93 Lille France June 14 17 1993 Rob Robbiano L 1985 Term orderings on the polynomial ring Pro ceedings of Eurocal 85 Linz Lect Not in Comp Sc 204 513 517 SB Stillman M and Bayer D Macaulay User Manual 1989 Available by anonymous ftp on zarinski harvard edu Sugar Giovini A Mora T Niesi G Robbiano L and Traverso C 1991 A sugar cube please or Selection strategies in the Buchberger algorithm Proc ISSAC 91 to appear TD Traverso C and Donati L Experimenting the Gr bner basis algo rithm with Alpi system In ACM Press editor Proceedings of the 33 1986 International Symposium on Symbolic and Algebraic Computa tion ISSAC 89 1989 Trav Traverso C 1988 Gr bner trace algorithms Proceedings of IS SAC 88 Roma Lect Notes in Comp Sc 358 125 138 Tr Trinks W 1978 Uber B Buchbergers Verfahren Systeme Alge braischer Gleichungen zu L sen J Number Th 10 475 488 Mo M ller H M 1989 To appear W Wilkinson J H 1959 The Evaluation of the Zeros of III conditioned polynomials Num
6. can also work with products orders and weight orders The default mode is lex In REDUCE a term order is specified by means of the torder command For example 26 torder gradlex 28 Since a monomial order depends also on how the variables are ordered REDUCE needs to know both the term order and a list of variables To indicate how the variables are ordered in a REDUCE command include a list of variables in the input For computing a Gr bner basis use the command groebner 27 torder lt order wanted gt 28 groebner polylist varlist or with 29 torder lt gradlex or revgradlex gt 30 g groebner polylist varlist 31 gb glexconvert g where polylist f fm and varlist 1 2n glexconvert converts the Gr bner basis calculated with torder gradlex or revgradlex into the corresponding Gr bner basis for torder lex It is in gen erally faster to calculate a Gr bner basis for torder lex with glexconvert If gltbasis is set on off by default the leading terms of the result basis are extracted They are collected in a basis of monomials which is available as value of the global variable with the name gltb Some other commands are preduce f polylist varlist gives the remainder of f on division by the poly nomials in polylist using the monomial ordering specified by torder and varlist gsplit f varlist computes It f and It f gsort f varlist prints out the terms of a polynomial according
7. given para metrically as m gi ti cond Stan Ta Gnt erea Emn If the gi are polynomials or rational functions in the variables tj the V will be an affine variety or part of one Find a system of polynomial equations in the xi that define the variety Note that problems 3 and 4 are inverse problems 3 Orderings on the monomials in k x n Let X By cee be a monomial where X z1 n and a Q1 Qn IN We note that we can reconstruct the monomial X from the n tuple of exponents a This establishes a one to one correspondence between the monomials in k X and IN Definition 1 An ordering on the monomials of k X is a relation gt on IN so that 1 gt is a total ordering on N 2 ifa gt B for every y in IN we hvea y gt Y 3 gt is a well ordering it means every nonempty subset of IN has got a smallest element under gt Let a and 8 be in IN We will use the three following orders a complete description of the orderings satisfying above conditions is given in Rob e Lexicographic Order we say a gt jez if in the vector difference a the left most nonzero entry is positive We will write X gt XP if a gt ez B Remark 1 We have x gt Iex 2 gt lex gt lex Tn If we work with polynomi als in two or three variables we will call them x y z rather then x1 x2 x3 We will also assume that the alphabetical order x gt y gt z o
8. ring k z1 n It permits us to determinate if a given polynom f belongs to F and if not to calculate his remainder modulo F Let k z be an univariate polynomial ring let F f z fm x be an ideal With the Euclidian algorithm it is easy to reduct a given polynom f z This method is based on the natural notion of ordering of terms in polynomials For a multivariate polynom there doesn t exist such a natural order MMXI Permission to copy is granted provided the title page is also copied 2 Problems concerning the algebra of polynomial ideals and geometry of affine varieties Below we summarize some those problems of Gr bner basis that are used in the subsequent applications see BCK and CLO Problem 1 The Ideal Description Problem Does every ideal I C klx amp n have a finite generating set In other words we can write I fi fs for some fi k x1 2n Problem 2 The Ideal Membership Problem Given f k x1 n and an ideal I f fs determine if f I Geometrically this is closely related to the problem of determining whether V f fs lies on the variety V f Problem 3 The Problem of Solving Polynomial Equations Find all common solutions in K of a system of polynomial equations Messern This is the same as asking for the points in the affine variety V fi fs Problem 4 The Problem of Implicitization Let V be a subset of K
9. zero on division then in f in g in gs Since I g1 9s there are constants Cia k such that 1 BDA i we 5 Let 6 max a multideg g ca 0 and let q be the sum of all terms in the expression f for f that contribute terms of multi degree 6 q X ciat 93 where for each i there is at most one a i such that 2g has multi degree 6 and we include only those terms in the sums We will also assume that among all possible expressions f for f we have selected one in which 6 is minimal There are two cases a If multideg f 6 so that not all the terms of multi degree 6 in f cancel out then in f in q in g in gs which is what we wanted to prove We are done in this case b If on the other hand multideg f lt 6 then the terms of multi degree 6 in f and hence q cancel By properties 4 q can be rewritten as q 5 dij S a gi ed ij for some constants d k However by the definition of the S polynomial f 5 Sg ed x S gi gj where 2 is a monomial The g gj give a remainder of zero on division by G by hypothesis Applying the division algorithm then multiplying by x97 we can replace each of the x S g gj by a combi nation gt gt aigi We claim that every term that occurs in this expression has multidegree less than 6 The reason is that in the expression gt gt 6 g 13 for the S polynomial given by the division al
10. 2 y y a ay ay 3 pass in f does not divides in q but in f2 so az ag in q in f2 0 41 y q q lin g in f2 fe ay yt x y4 p 4 pass neither in f nor in fz divides in q so r r in qg 0 y y g q in g 0 and the main loop terminated The result of the division algorithm is J uf tafe r or wy ay y a Hay y e y Now let us perform the same division changing only the order of the pair of polynomials of divisors We start with f z yt fa r xy f xy k z y Then a 0 a2 0 r 0 q f x y After 6 pass the algorithm terminates The final result is f a f az2f2 r or xy zty ry a yl eytt y a yt i O a ry y Remark 3 In the previous example the a and the r can change if we simply rearrange the fi The a and the r may also change if we change the monomial ordering Remark 4 The nicest features of the division algorithm in kl x is the way it completely solves the ideal membership problem see Problem 2 and section 6 1 Do we get something similar here Corollary of Theorem 1 If after division of f by F fi fs we obtain a zero remainder then f afi asfs so that f fip fo The previous corollary gives a sufficient condition for the ideal membership Counter example Let f zy 1 fo y 1 k z y with the lexico graphi
11. Gr bner Basis and Applications A Survey 1 Introduction All the polynomial ideals are associated with varieties To operated with ideals we will need to illustriate the computation of the basis of the ideal Hironaka in 1964 see Hir established the existence of the standard bases for the local properties for the ideals of formal power series However it was Buchberger who in his Ph D thesis see B1 first presented an algorithm to perform the required transformation in the context of polynomial ideals in the global cases What is a Gr bner basis The Gr bner basis is a finite set of multivariate polynomials solves the following problem see B4 e given a finite set F of multivariate polynomials over a field construct a finite set F of multivariate polynomials such that p p and gt fy is Church Rosser Where for a set F of polynomials p is the ideal congruence modulo the ideal generated by F ie f p g amp f g ideal F and gt p is a certain Notherian reduction relation on polynomials introduced by F with the property that the reflexive symmetric transitive closure of gt is equal to p If F is the Grobner bases of F the Church Rosser property guarantees that for arbitrary polynomials f g the congruence f p g can decided by computing normal forms of f and g modulo gt p and checking for syntactic equality A Gr bner basis is used to describe an ideal F f fm of the poly nomial
12. U S until G G Proof If G G the algorithm terminates and all S p N 0 so G is a Gr bner basis by proposition 4 After each pass through the main loop 4 in G lt in G 15 since G C G Futhermore if after a pass through the loop G 4 G then in G C in G but they not equal The reason is that the initial forms of the S that were adjoined to G in the pass cannot lie in in G otherwise those initial forms would have been removed in the computation of the remainder on division by G By contraposition if we ever have in G in G then G G By the the ideals in G formed in successive iterations of the loop are part of an ascending chain of ideals in k x1 x But klx 2n is a noetherian ring so after a finite number of iterations the chain will stabilize As result the algorithm will always terminate e Remark 7 A constructive proof is given of the terminantion of the algo rithm for computing Gr bner bases in polynomial rings over a construc tively noetherian ring see JL They combine the constructive approach of Richman and Seidenberg with the Grobner basis methode and they introduce a new induction principle proposed by Per Martin Lof in the definition of noetherian rings The adds of polynomials in J may introduce an element of redundancy Note as a first improvement that once a remainder S p n 0 the remainder will stay zero even if we
13. c order Diving f xy x by F fi f2 we have ay z y zy 1 0 4 1 2 y by F fa fi ry x z y 1 0 2y 1 0 From the second calculation we known that f fa fi However we see by the first calculation that even if f f fs it is still possible to obtain a non zero remainder on division by F f fs if the fi is ordered incorrectly or the fi themselves are wrong in some way It is too much to hope that f has a well defined remainder of f on division by the ideal I since the remainder can change if we simply list of generators of I in a different order 5 Hilbert Basis Theorem and Gr bner bases 5 1 The Hilbert basis theorem Our aim here is to study a certain familly of ideals which will be usefull for constructing the Gr bner bases Our considerations will be also lead to ideal with good properties relative to the division algorithm The key idea we will use is that once we have chosen a monomial ordering each fe kle x n has a unique initial form in f Definition 2 An ideal I in klx xn is a monomial ideal if this is generated by collection not necessarily finite of monomials Definition 3 Let I be an ideal in k z1 n other than 0 Let note by in I the set in f f I and by in I the ideal generated by the elements of in I Remark 5 in f1 in ft and in I can be different ideals In gen
14. eral in fi in fe C in D Lemma 1 Membership problem for monomial ideals Let A be a subset in IN possibly infinite Let I a a A be a monomial ideal The fe I iff every term in f is divisible by one of x Proof gt Let f DL x where gi klx n Every monomial x of f has 8 a y for some a and y Zo Easy e Theorem 2 Every monomial ideal I generated by a finite collection of monomials e Theorem 3 Hilbert basis theorem Every ideal I in k z1 n has a finite generating set That is I g gr for some g gr I Proof By the previous theorem the monomial ideal in I generated by a finite collection of monomials let x x Let g I We can see that each x is actually the leading monomial of gj t La i 5 Fiin g j l fj kla 2n but is a monomial then z c m in g where c k some monomial m and g J Hence each of the generating monomials of in I is the leading monomial of some element 9 of I Then in Z in g1 n 9e We can see now our claim that I g1 gt for some gi gt k z1 n The fact that g1 9 C I is easy Now IC g g Let f I Using Divisor algorithm f G where G g1 g we can remove in f with some multiple of one of the gi because in f in G in g in g But f m gel At the termination of the divisi
15. f some power products t i e they are polynomials The vector g1 gs is called syzygy if F fi fs Interpreting every S polynomial reduction to 0 as syzygy we can predict every zero reduction provided we known a suitable basis of the module of syzygies Notation Let f g F f tg if f g or there exists a sequence g1 9 g such that SP 9 rel Criterion 1 Let f g klx x such that Iem Ilm f lm g Im f im g then SCH 0 24 Criterion 2 Let f g h k x 2n be such that in h divides Icm in f in g then S f g is linear combination with polynomial coefficients of S f h and S h g If in the Buchberger s algorithm we arrive at a collection of polynomials P containing three polynomials f g h satisfying in h divides lem in f in g and it has already been determined that S f h 0 and S h g 0 then it is not necessary to reduce S f g modulo P as well By the crite rion 2 S f g yields a syzygy that is already in the collection of syzygies generated by S f h and S h g 25 8 APPENDIX II The computer algebra system REDUCE 3 5 by F Rouillier Univ Rennes 1 WARNING This chapter gives any explanations how to use REDUCE and his Gr bner basis package It may not be enough if you want to discover this computational system For more informations see in an user s manual 8 1 Loading and quitting If you want to work with REDUCE you
16. gorithm the initial form of the S polynomial appears in exactly one term in the sum J P g and the other terms are produced by subsequent steps in the algorithm These subsequent terms are strictly less than the initial form in our monomial order This means that all the terms in gt aig g ii X bigi have multi degree 6 Subtituting back in equation f we get an ex pression for f of the same form as f but that involves only terms of multi degree less than 6 This contradicts the way was chosen so this case actually does not occur e Example 2 Let I fi fo x 2xy xy 2y x using the grlex Then fi f2 is not a Gr bner basis for I since x in I but 2 in fi in f2 To produce a Gr bner basis one natural idea is to try first to extend the original generating set to a Gr bner basis by adding more polynomials in J In one sense this adds nothing new and even introduces an element of redundancy However the extra information we get from a Gr bner basis more than makes up to this S fi f2 x I but its remainder on division by F fi f2 is x which is nonzero Hence we should include that remainder in our generating set as a new generator called f3 Thus we let F fi fo f3 We test to see if this new set is a Gr bner basis for J using the theorem 4 which gives a completely algorithmic way to decide if a set is a Gr bner basis We compute S fi fe fs so S fi
17. have to call it with REDUCE In REDUCE all command ends with a semicolon The promt has the follow ing form 1 lt instruction gt If you want to load the Gr bner basis package call it with 2 load groebner If you want to quit REDUCE write 3 bye 8 2 Declarations An number from the type integer may be in principle as long as wanted There exist some reserved variables For example e base of natural loga rithm i 4 1 infinity nil synonym of zero pi If you want to do an assignment for a variable you can do it as following l a x y 3 z 2 A list can be created with 2 ListName a b c d Lists are very usefull in particulary in the Gr bner basis package There exist some operations with the list 3 part ListName n which gives the n element of the list or an error 4 length ListName which gives the length of the list 5 rest ListName returns its argument with the first element re moved or an error 26 6 a b c or 7 a cons b c returns a b c 8 append a b c d gives a b c d 9 reverse a b c restitues c b a Array declarations in REDUCE are similar to Fortran dimension state ments For example 10 array a d1 d2 d3 Array indices each range from 0 to the value declared All array elements are initialized at 0 at declaration time If an array is referenced by an index outside its range an error occurs The command define allows a user to supp
18. in but linear algebra is more efficient let us recall that the quotient of a polynomial 19 ring by a zero dimensional ideal is a finite vector space it has the irre ducible monomials for a Gr bner basis as a linear base the expression of a polynomial on this base is simply obtained by reducing this polynomial finally the elements of a reduced Gr bner basis are obtained by expressing the minimal for divisibility reducible monomials on this linear base Thus the change base algorithm FGLM is the following Generate the monomials by increasing new ordering and reduce them by old base If an obtained polynomial is linearly independent from the previous gener ated ones then the corresponding monomial is irreducible for the new base If this obtained polynomial is dependent from the previous ones then the dependence relation between monomials gives a member of the new Gr bner basis Discard from the generating process all multiples of the corresponding monomial which is the leading monomial of the new Gr bner basis member Stop when all monomials have been generated or discarded This algorithm stops eventually because the number of irreducible monomi als and the number of leading monomials in a minimal Gr bner basis are both finite The computations are mainly linear algebra on the base of irreducibles mono mials for old Gr bner basis and reduction operations The data structures may be managed in order tha
19. it REDUCE ws calls the last result and ws N calls the result which was calculated in the prompt nummer N if it exist 27 8 4 Files If you want to save some results in a file write 16 out FileName red 17 f g h 18 shut FileName red where FileName red is the name of the file and f g and h are the saved results If you want to load a file call it with 19 in FileName red 8 5 Options switchs on and off declarations If you work with integers the default calculating mode is integer If you want to have a rational result you must ask it with 20 on rational By default results are given in the following form z 3 x2 y 1 There can be written like x 2 3 a2 y 1 This is necessary if you save the result in a file and need to use it again latter else REDUCE can t read it For this write 21 off nat With 22 on time the computer indicates the time needed for executing an instruction after each command The time depends on the computer system 23 on demo stop after each instruction if a command contains many instructions 24 on fact factorises the expressions when it is possible 8 6 The Groebner basis package The Gr bner basis package is called in REDUCE with 25 load groebner In REDUCE a monomial ordering is called a term order REDUCE knows most of the possible monomial orderings in particular lex gradlex and revgradlex which are so named REDUCE
20. ly a new name for any iden tifier or replace it by any well formed expression Its argument is a list of expressions of the form lt identifier gt lt number gt lt identifier gt lt operator gt 8 3 Statements The group statement is a construct used where REDUCE expects a single statement but a series of actions needs to be performed It is formed by enclosing one or more statements between lt lt and gt gt The statements are executed one after another The construction begin end is possible too It is named a compound statement Conditional statement 11 if lt boolean expression gt then lt statement gt else lt statement gt for statement 12 for lt var gt lt number gt step lt number gt until lt number gt lt action gt lt expr gt or 13 for each lt var gt in lt list gt lt action gt lt expr gt where lt action gt do product sum collect join Instead for j a step 1 until b do it is possible to write for j a b do while do and repeat until 14 while lt boolean expression gt do lt statement gt 15 repeat lt statement gt until lt boolean expression gt return lt value gt permits us to restitue a value calculated in a compound or if or group statement With end it is possible to stop an execution without quitting REDUCE And CTRL Z stops a programm without quitting REDUCE with CTRL C the programm is stopped but we qu
21. n the variables is used to define the lexicographic ordering unless we explicitly say otherwise Examples a 1 2 0 gt z 0 3 4 since a 8 1 1 4 b 3 2 4 gt ez since a p 0 0 3 c 1 0 0 gt x 0 1 0 0 Spe gt lex 0 1 e Graded Lex Order we say a gt gradlex if a So a gt 8 So Bi or a 8 and a gt ez B i 1 i 1 we have also T gt gradlex T2 gt gradlex Bar gt gradlex In Examples a 1 2 0 gt gradlex 3 2 0 b 1 2 4 gt gradlex 1 1 5 e Graded Reverse Lex Order we say amp gt revgradlex B if n n la Soa gt B 55 Bi or a 8 and i l i l the right most nonzero entry in a 6 is negative we have also z gt revgradlex 2 gt revgradler gt revgradlex Tn Examples a 4 7 1 gt revgradter 4 2 3 since 4 7 1 12 gt 4 2 3 9 b 1 5 2 2 gt revgradlex 4 1 3 2 since a b 3 4 1 0 Remark 2 The latter of these ordering may appear as rather strange but it should be emphasized that it is generally the one for which the computation of a Gr bner basis has the best theoretical and practical complexity Proposition 1 These three orderings are monomial orderings e Some Examples Let p 4ry z 42 523 7x72 k z y z Then a with respect to the lex order we could have p 5r 7x72 Aay z 42 b with respect to the gradlex order
22. nd it is independent of the ordering of G used in the Division algorithm Proof Let f q r ra be two expressions both obtained by division but with the element of G ordered by different ways Then r r2 q q I Ir ra 0 since G is a Gr bner basis of J the leading monomial of every element and the r r2 of I is a multiple of the leading monomial of some element of G This contradicts in the fact that none of the monomials of r or ra or r ra is a multiple of the leading monomials of any of the elements of G e Proposition 4 Let G be a Grobner basis for I and f I fel ff 0e Remark 6 This corollary solves the Ideal membership problem Pro blem 2 section 2 and section 6 1 This was one of Buchberger s original intentions Proposition 5 If G is an ideal basis for I with the property f 0 for all the f I then G is a Gr bner basis for I e 5 3 S polynomials The main algorithm for computing Gr bner bases is Buchberger s one which he introduced in 1965 in his thesis B1 B2 B3 B4 This algorithm is developed from two basic tools the reduction or division process and the critical pairs or S polynomials Definition 5 Let f g in k x1 n be non zero polynomials 1 If md f a and md g then let y be 1 n where yi mazx a for each i We call x the least common multiple of Im f and Im g and we note x lem lm f Im g
23. nential time To appear in Proceedings of AAECC 7 Toulouse 1989 CLO Cox Little O Shea Ideals Varieties and Algorithms Undergrdu ate Texts in Mathematics Springer Verlag 1992 D1 Davenport J H 1987 Looking at a set of equations Technical report 87 06 University of Bath 31 DST Davenport J H Siret Y and Tournier E 1986 Calcul Formel Syst mes et Algorithmes de Manipulation Alg briques Masson En glish translation Computer Algebra Academic Press 1988 Fau Faugere J C On line documentation of GB Available at http posso ibp fr Gb html FGLM Faug re J C Gianni P Lazard D and Mora T 1988 Ef ficient computation of zero dimensional Gr bner bases by change of ordering Technical Report LITP 89 52 submitted to J Symb Comp Fit Fitch J Solving algebraic promblems with Reduce J Symb Comp 1 211 277 1985 Gian Gianni P 1987 Properties of Gr bner bases under specializa tions European Conference on Computer Algebra Leipzig GDR 1987 J H Davenport ed Lect Notes in Comp Sc 378 293 297 GM Gianni P and Mora T 1987 Algebraic solution of systems of polynomial equations using Gr bner bases Applied Algebra Algebraic Algorithms and Error Correcting Codes AAECC 5 Menorca Spain 1987 Lect Notes in Comp Sc 356 247 257 GMRT Gianni P Mora T Robbiano L and Traverso C 1994 Hilbert functions and Buchberger algorithm Submitted fo
24. om s coding method see LRR 23 7 APPENDIX I Grobner bases Computation Using Syzygies The most time consuming part of the Algorithm 2 see section 5 4 is the reduction of the S polynomials If an S polynomial reduces modulo F where F is a finite ideal basis of a polynomial ideal k x xn to the zero polynomial its computation and reduction give no contribution to the final Gr bner basis Such zero reduction can be avoided if a criterion is available which predits that the S polynomial reduces to 0 Different kinds of criteria for avoiding many of these zero reductions are developped by Buchberger B4 The crucial idea for involving syzygies in the detection of superfluous zero reductions can be easily understood by using an observation by Lazard Lal Since an ideal can be considered as an infinite dimensional vector spase an ideal possesses simultaneously ideal bases and Gr bner bases Lazard pointed out the connection between Gr bner bases and linear bases of the same ideal Buchberger s algorithm can be considered as a triangularisation of a linear basis by Gaussian elimination The reduction of a polynomial to zero means a linear dependence of this polynomial on the polynomials employed in the reduction procedure Since all polynomials are here of type tifi fi F ti a power product the linear dependence relation can be written as a syzygial relation Irak 0 JER where the g are linear combinations o
25. on our result will be t f 5 aigi 0 i 1 for some a klx xn But the remainder is zero then f 91 59t 5 2 The Gr bner bases Some Properties Definition 4 Fiz a monomial order A finite subset G g1 9r of an ideal I is said to be a Gr bner basis abbr GB or standard basis if in g1 n gr in Z Corollary 1 Fix a monomial order Then every ideal I C klx amp n other than 0 has a Gr bner basis Furthermore any Gr bner basis for I is a basis of I Proof Consequence of Hilbert Basis Theorem e For ideals generated by linear polynomials a Gr bner basis for lex order is determined by the row echelon form of the matrix made form the coefficients of the generators Proposition 2 Let J C R 21 2 be a ideal generated by the rows of A z1 2 n where A is anmxn matrix is a row echelon form The given generators form a Gr bner basis for J with respect to a suitable lexicographic order e Example Consder the ideal J g1 92 x z y z The g and g2 form a Gr bner basis using lex order in R x y z since in J a z and in gi in g2 x z proof Notice that the generators for the ideal J come form a row echelon matrix of coefficient 10 1 0 1 1 10 Proposition 3 Let G g gr be a Gr bner basis for an ideal I C klx 1 2n and let f I The remainder fC of the reduction of f by G is unique Division algorithm a
26. r results until the interpolated one does not change anymore Practically this method works well because almost all primes are of good reduction if primes of the order of the machine word size are used bad primes are very rare However the result is only obtained with a very high probability not proved The second method consists in doing only a few modular computations and in eliminating from the trace the S polynomials which are not useful for computing the Gr bner basis because they reduce to 0 or to a polynomial which is not used for the computation of the ones which appear in the final reduced base Then this shorter trace is used for conducting non modular computations without wasting time for computing polynomials equal to 0 With this method also the result is not proved but the polynomials which are obtained are certainly in the ideal generated by given polynomials 18 For proving that the obtained result is correct further computations are needed Verification that input polynomials reduce to 0 by the obtained base This is rather easy Verification that the polynomials of the base are in the ideal generated by the input This is only needed for first method Verification that the result is a Gr bner basis The last two verifications may be almost as difficult as computing the Gr bner basis base by not modular method Several criteria for avoiding them may be found in Trav A further criterium for the last
27. r publication GTZ Gianni P Trager B and Zacharias G 1988 Gr bner bases and primary decomposition of polynomial ideals J Symb Comp 6 149 167 Hir Hironaka H 1964 Resolution of Singularities of an Algebraic Va riety over a Field of Characteristic Zero I II Ann Math 79 pp 109 326 Hea Hearn A Reduce user s manual Version 3 3 The RAND Corp report cp 78 edition Jully 1987 JL Jacobsson C L fwall C 1991 Standard Bases for general coeffi cient rings and a new constructive proof of Holbert s basis theorem J Symb Comp 12 337 371 32 JS Jenks R Sutor R Axiom the Scientific Computation System Springer Verlang 1992 JSW Jenks R Sutor R Watt M Scratchpad II An abstract databype system for mathematical computation In R Jan en editor Trends in Computer Algebra Proc Internat Symp pages 12 37 Bad Neue nahr May 1987 Springer L N C S 296 KFF Kobayashi H Fujise T and Furukawa A 1988 Solving systems of algebraic equations by general elimination method J Symb Comp 5 303 320 KMH Kobayashi H Moritsugu S and Hogan R W 1988 On Solving Systems of Algebraic Equations Proc ISSAC 88 Lal Lazard D 1983 Gr bner Bases Gaussian Elimination and Reso lution of Systems of Algebraic Equations Proc EUROCAL 83 Lect Notes in Comp Sci 162 Springer 146 157 La2 Lazard D 1989 Solving zero dimensional algebraic systems To
28. rem 1 Division Algorithm in k x 2 Let F fi fm be a ordered by gt m tuple of polynomials in k 1 n Then every f k 1 n can be written as FOr fib tet where a and r are in klx amp n and there doesn t exist j 1 lt j lt m such that in f divides r We call r a remainder of F by division by F e Algorithm 1 Division Algorithm see CLO input fiers Im f output a1 Qm 7T Main Idea Pick off the initial form of the f each time while q 0 do eae pickterme false while j lt m and pickterme false do if in f divides in q then aj aj in q in f q q in q in f fj pickterme true else j j 1 if pickterme false then r r in q q q in q end A important property of the division algorithm in k x is that the remain der is uniquely determinated But this can fail when there is more than one variable and the decomposition modulo F depends on the ordering of fi fm see below Example CLO Let fi zy f2 x yt f xy k z y with the lexicographic order Then a 0 az 0 r 0 q f r5y 1 pass we see that in fi divides in q so ay a in g in f 0 2 y xy q q in g in fi f 2 y a y a zy ay The remainder r stay 0 2 pass in f divides in q so ay a in q in f a y y q q in g in hi fi
29. rences Alp Alpi a system for experimenting with Buchbergeralgorithm alpha version in Common Lisp available by anonymous ftp in gauss dm unipi it 131 114 6 55 B1 Buchberger B 1965 Ein Algorithmus zum Auffinden der Basise lemente des Restklassenringes nach einem nulldimensionalen Polyno mideal Ph D Thesis Innsbruck B2 Buchberger B 1970 Ein algorithmisches Kriterium f r die L sbar keit eines algebraischen Gleischunssystem Aeg Math 4 374 383 B3 Buchberger B 1979 A Criterion for Detecting Unnecessary Re ductions in the Construction of Gr bner Basis Proc EUROSAM 79 Lect Notes in Comp Sci 72 Springer Verlag 3 21 B4 Buchberger B 1985 Gr bner Bases an Algorithmic Method in Polynomial Ideal Theory In Recent trends in multidimensional system theory Bose Ed Reidel BCK B Buchberger G E Collins and B Kutzler 1988 Algebraic Methods for Geometric Reasoning Ann Rev Comput Sci 1988 3 85 119 CGG B Char K Geddes G Gonnet B Leong M Monagan and S Watt Maple V Library Reference Manual Springer Verlang 1991 3 printing 1993 CGH1 Caniglia L Galligo A and Heintz J 1989a Some new effectivity bounds in computational geometry Proceedings of AAECC 6 Roma 1988 Lect Notes in Comp ci 357 Springer Verlag 131 152 CGH2 Caniglia L Galligo A and Heintz J 1989b How to compute the projective closure of an affine algebraic variety in subexpo
30. sis f1 fo f3 fa fs is not reduced since a Some of the leading coefficients are different from 1 However this is not a serious objection we can simply multiply all the generators by suitable constants to make this true b For example in f1 x in f3 We can dispense with f3 the reduced Gr bner basis Similarly since in f2 z y 1 2 zin f we can also eliminate fa There are no futher cases where the initial form of a generator is a multiple of the initial form of another generator Hence fs 2 fa zy fs y 1 2 r do form a reduced Gr bner basis for I 5 5 Improvements for the Gr bner bases For an efficient implementation this algorithm needs several improvements which concern Criteria for avoiding to compute S polynomials for which one may predict that they reduce to 0 These criteria may avoid to compute up to 90 of the S polynomials but improvements are yet needed because 90 of the remaining one may reduce to 0 see also Appendix I Strategies for choosing the S polynomials to compute first and for selecting the polynomial by which to reduce when there is a choice The strategy which is used has a big influence on the number of S polynomials to compute and on the size of the coefficients to handle both parameters are critical for efficients computations Sugar The way of normalizing the polynomials which appear they are defined up to the multiplication by a constant When dealing with pol
31. t the number of operations of this algorithm is polynomial in the number of irreducible monomials number of solutions counted with multiplicities If the size of the coefficients is taken into ac count the complexity of this algorithm may be exponential in the number of variables but only for very irregular sets of irreducible monomials for most entries the complexity is polynomial in the number of irreducible monomi als These complexity results are of practical interest for most entries the time needed by change base algorithm is much less than the time needed for computing the base for the degree ordering 2 CHANGE BASE ALGORITHM BY THE ALGEBRA STRUCTURE A new algorithm for computing Gr bner basis by change of ordering that seems faster than the two previous ones FGLM and GMRT The main 20 idea of this algorithm is to use the algebra structure of the quotient space in stead of linear algebra This algorithm is proposed by Jean Charles Faugere in 1994 It has made a very first implementation of the algorithm in AXIOM 5 6 Some computational languages for the Grobner bases 1 MAPLE V 2 Very slow see CGG To access to the Gr bner basis package type gt with grobner 2 MATHEMATICA 2 2 1 Slower than Maple To access to the Gr bner basis package type In 1 GroebnerBasis polylist varlist 3 REDUCE 3 5 Fit and Hea We notice that REDUCE is faster with small homogeneous systems but cannot comp
32. to the term order gspoly f g varlist calculates a S_polynom S f g greduce f polylist varlist gives the remainder of f on division by the Gr bner basis of the ideal generated by the input polynomials preducet f Gb basis can be used to find the quotients in the division al gorithm gzerodim Gb basis varlist tests a Gr bner basis to see if the equations have finitely many solutions over an algebraically closed field groesolve polylist varlist attemps to find all solutions of a system of poly nomial equations idealquotient polylist expr varlist calculates the quotient of an ideal and an expression hilbertpolynomial polylist varlist gives the Hilbert polynomial of an ideal 29 Remark 8 preduce and groebner are the most used commands in the RE DUCE Gr bner basis package If the polynomial used in preduce or groebner have integer or rational coefficients REDUCE will assume that we are work ing over the field Q There are no limitation in the size of the coefficients Another possible coefficient field is the Gaussian rational numbers Q i Use the command 32 on complex before computing the Gr bner basis Similary to compute over a finite field with p elements use 33 on modular setmod p REDUCE can also work with coefficients that lie in function rational fields To tell REDUCE that a certain variable is in the base field a parameter omit it simply from the variable list varlist in the input 30 9 Refe
33. ute the cyclic 6 because the Buchberger algorithm is not implemended with sugar strategy To access to the Gr bner basis package type 1 load groebner REDUCE is more performant than 1 and 2 because it has the fastest implementation and offers most possibilities see also Appendix II 4 Axiom 4 1 JSW JS Seems to be the best general computer al gebra system for solving polynomials systems essentially because of a goal implementation of the sugar strategy However computations with Z2 pZ are not very fast 5 MACSYMA 6 COCOA Spezialized program for Mac 7 ALPI 1 95 Alp TD results found in the MRT 8 Mas 0 7 A lot of function related to Gr bner basis very slow 9 MacAuLaY SB Very efficient for modular computations No support for the integer case 10 GB Fau From Jean Charles Faug re is the most efficiently actually As a conclusion we give the class of each systems as it appear in PoSSo 71995 in Paris by Jean Charles Faugere 21 MATHEMATICA 4 MAPLE 4 5 MAS 4 5 MACAULAY x REDUCE 5 ALPI 6 AXIOM 6 GB 7 6 Applications of Grobner bases Let us return to the basic problems see section 2 and see to what extent being able to compute Gr bner bases furnisches solutions 6 1 The Ideal Membership Problem As we mentioned in Remark 6 knowing a Gr bner bases G g 9s for an ideal J gives an algorithmic solution to the ideal membership prob lem We need onl
34. verification which does not appear in this paper may be useful in the case of a finite number of solutions which are simple Use the guessed base for computing the solutions and verify that these solutions are effectively solutions of the given system This a posteriori verification works because if a set of polynomials is not a Gr bner basis there are too many irreducible monomials and thus too many guessed solutions 5 5 2 Change base algorithms 1 CHANGE BASE ALGORITHM BY LINEAR ALGEBRA see also La2 and FGLM The second improvement to Gr bner basis algorithms is the algorithm for changing orderings for Gr bner bases FGLM It works only in the zero dimensional case finite number of solutions Its main idea is that Buchberger s algorithm is much more efficient with degree orderings gradlex revgradlex than with lexicographical ordering lex on the other hand lexicographical ordering is more suitable for comput ing the solutions of a system Tr the degree orderings more precisely the revgradlex order gives only a general description of the ideal dimension number of solutions Hilbert function but not the solutions Thus it is much more faster to compute the base for a degree ordering by Buchberger s algorithm and to deduce from it the lexicographical base This made first by means of linear algebra and recently by using Hilbert functions GMRT For this purpose one could use Buchberger s algorithm aga
35. we could have p 7x 2 Any z 5x 42 c with respect to the revgradlex order we could have p 4ay z 7x22 5a 42 Definitions 1 Let f 0 Car be a nonzero polynomial in klx amp n and let gt be a monomial order The multidegree of f is md f maz a N ca 0 The leading monomial of f is Im f 2 with coefficient 1 The leading coefficient of f is If Amals k The leading term of f is in f Ic f Im f 4 A division algorithm in klr n Reducing a monomial m by a polynomial p consists in replacing m by m iment hata if m is a multiple of the leading monomial Imon p of p or in doing nothing if it is not a multiple Reducing a polynomial p by a set of polynomials S consists in reducing the monomials in p by the polynomials of S while it is possible For easy reasons of efficiency the biggest for the monomial ordering monomials of p have to be reduced first As an example it is worth to remark that reducing an univariate polynomial by another consists in computing the rest of euclidean division It should also be noted that in the general case the reduction depends on some choices and thus that the reduction has not an uniquely defined result We can use any one of our orderings on monomials see section 3 to for mulated a division algorithm for general polynomials extending the usual algorithm in k x Let gt be a fixed monomial order on IN Theo
36. y compute a remainder to answer this question since fel fe 0 Example Let I fi fe xz y 2 2 Rlz y 2 and f Ag y z yf 3z we use lex order Our question is f I First we check if the generate set f1 fo of ideal is a Gr bner basis of I S fi f2 27y 2 and in S f f2 27y If fi f2 is a Gr bner basis for J then in I also contains in S f1 f2 xy see proof of the theorem 4 section 5 3 But y amp in f1 in fo z x so the set f1 fo is not a Gr bner basis of I Hence we compute the Gr bner basis of I G fo fs fa fi fs a 2 F EU z3 ry z zz T y y 2 22 We may now test polynomials for membership in J Diving f by G we find f 0h Ofo 42 f3 Ofs 1fs 0 By the proposition 4 we have that f I Note that the G is a reduced Gr bner basis for J since both conditions of the definition 6 are satisfied Consider now the polynomial f xy 5z a An easily manner to answer in our question if f I is the following if f I then in f in G see proof of theorem 3 section 5 1 but in f xy in G 3 x7y ryt xz y so f I 6 2 The Problem of Solving Polynomial Equations We will investigate how th Gr bner basis technique might be apllied to solve systems of polynomial equations of several variables The real solutions of the system are coding by the interval method or by the Th
37. ynomi als over the rationals it is clearly better to remove denominators for 17 working with integer coefficients but one has to remove the gcd of the coefficients at some steps The data structures which lead to efficient computations The state of the art concerning these optimizations appears mainly in Su gar However the research in this field is active and many improvement are implemented in some systems without being published In spite of these improvements Gr bner bases computations need often very long computations and a lot of memory space Thus further improvement are yet needed We describe now two of them 5 5 1 Modular computations see also La2 As the size of the coefficients is frequently the limiting factor in Gr bner bases computations it is natural to use modular technics However there is no criterium for detecting primes of bad reduction even if it is easy to prove that there are finite in number Also there is no sharp bound on the size of the coefficients of the result which makes interpolation questionable Both difficulties are solved by tracing i e by remembering the leading monomials of the polynomials which appear the S polynomials which are computed and the polynomial by which they are reduced Trav Such a trace may be used in two ways The first one consists in doing several modular computations throwing away those for which the trace differ and incrementally interpolate the modula
Download Pdf Manuals
Related Search