Canonical discussion of polynomial systems with parameters
Contents
1. Y The algorithm is able to represent the perfect specifications Y of the different cases in a canonical form leading to a complete canonical discussion and a true partition We show that for a given ideal and monomial order there exists only a few set of possible descending chains of varieties even if there does not always exist a unique one Even so the representation of the cases can be described by a canonical representation independent from its situation in the tree or chain The partition of K is almost independent of the particular descending chain It is unique and canonical whenever the elements of the partition correspond to different cases that cannot be summarized into a single one for example whenever they have all different lpp sets In some discussions it happens that some cases could be summarized into a single one Even if the actual implemented algorithm does not make this automatically it is always possible to do it externally from the output of the tree Frequently then this can also be realized using a different strategy with DISPGB A first implementation of the algorithm based on the definition of special cases given in MaMo05 was distributed on the web Using it a counter example has been provided to me by Wibmer Wi06 that showed that the definition of special cases given in MaMo05 was insufficient and give rise to erroneous discriminant ideal in some problems In this paper we have corrected this point and no2. Ed R del la Llave L Petzold and J Lorenz IMA Volumes in Mathematics and its Applications Springer Verlag 118 2000 1 29 SaSu03 Y Sato and A Suzuki An alternative approach to Comprehensive Gr bner Bases Jour Symb Comp 36 2003 649 667 SaSuNa03 Y Sato A Suzuki K Nabeshima ACGB on Varieties Proceedings of CASC 2003 Passau University 2003 313 318 Sc91 E Schonfeld Parametrische Gr bnerbasen im Computeralgebrasystem ALDES SAC 2 Dipl thesis Universitat Passau Germany May 1991 192 W Sit An Algorithm for Solving Parametric Linear Systems Jour Symb Comp 13 1992 353 394 We92 V Weispfenning Comprehensive Gr bner Bases Jour Symb Comp 14 1992 1 29 We03 V Weispfenning Canonical Comprehensive Gr bner bases Proceedings of ISSAC 2002 ACM Press 2002 270 276 Jour Symb Comp 36 2003 669 683 Wi06 M Wibmer Private communication Gr bner bases for families of affine schemes http relationsproject at tt 2006 18
3. I0 xd are Y V Ji 1 V Jji For the last terminal vertex q 1 0 p 0 it is You1 V Jj V V 1 V Jg Formula 1 gives a discriminant chain of descending varieties associated to the polynomial ideal J as it defines the regions of K space having different reduced Gr bner bases The strict inclusions in the chains arises as a consequence of Y V J 1 V J being non empty as it contains the generic case g i 4 Canonical Character of the Discussion Note that even the first tree T I gt z gt a built by BUILDTREE provides a finite partition X X1 Xp of K and the corresponding G GRGB X R r l BUILDTREE is algorithm depending and so a different partition A Xp X Xi using a different strategy in DISPGB But the union of the sets specified in the cases corresponding to a unique GRGB specializing to the reduced Gr bner basis of the specialized ideal with the same lpp set must be the same in and in X as these sets are not algorithm depending The rebuild process groups sets of X s having a unique GRGB that specializes to the reduced Gr bner basis of the specialized ideal with the same lpp s into a single Y 12 Moreover CANPERFSPEC provides a canonical description of the Y Thus when REBUILDTREE finishes with a partition where none of the generic reduced Gr bner bases are equivalent by specialization either they have different lpp sets or they do not specialize in the same
4. N Add J to vertex n of T SsiCspc Place at vertex 0 ud 0 1 of T Zo CANPERFSPEC J J the canonical representation the basis By of T Hang from the null branch of vertex 0 zm 0 of T the subtree of T starting with vertex 0 e 0 in T rewrite it by adding the null condition J using REDSPEC some of the vertices v in T with lpp Ipp will disappear in T because they become incompatible UNTIL the whole rebuilding is done END Table 3 REBUILDTREE algorithm 3 hang at the non null branch the perfect specification X 0 Jo representing the set Yo K N V Jo or better its canonical representation provided by CANPERF SPEC 4 hang from the null branch of the new rebuilt tree the old tree T 1 To do this add the null condition Jg to the reduced specifications in all the descending vertices use REDSPEC to recompute the specifications reduce the bases using the new specifications Given I and the order gt z the specification of the absolute generic vertex g 0 satisfies X 0 K by Theorem 3 and its lpp set is intrinsic by Gianni s Theorem Gi87 Thus Vo is also intrinsic because U X5 0 is the region of K 7 containing not generic special cases and this does not depend on the algorithm So the radical of the top discriminant ideal is also intrinsic We have already proved that it is equal to Weispfenning We03 top discriminant ideal 10 Spc SPECCASES n Inp
5. in the examples Let G gb 1 gt z be the reduced Gr bner bais of J computed wrt the product order gt z a This is a tentative Comprehensive Gr bner Basis of J The canonical Gr bner system obtained by DISPGB can be used to complete it to a true CGB that will then also be Canonical For this it suffices to verify for which cases and polynomials no polynomial in G does specialize to it For each of them we can compute pre images in J using an 13 appropriate algorithm This will be discussed in detail in another paper 5 Examples 5 1 Example 1 Consider the following linear system with ideal I x cy bz a cx y az b bz ay z c having three parameters Take monomial orders lex z y z and lex a b c DISPGB obtains the following discriminant ideal chain Jo a b c 2abc 1 Jj bte bt bt H b c eac act bc b bc b abc ab c c ab ac b c bc3 a b c 2abe 1 Jo 2 1 a bd Jag e 1 b 1 a bc with Jo amp J amp J2 amp Ja Decomposing the associated minimal varieties using CANPERF SPEC we have V Jg V c b 1 2acb a V I V a c b 1 UV c b a 1 UV c a b 1 UV b c a 1 U UV a b c 1 UV a b c 1 r U r2 U rs Ur4 Urs U rg V a b c 1 UYV a b c 1 2 r5 Ure V J V a 1 b 1 c 1 UV a 1 b 1 c 1 UV a 1 b 1 c 1 U EAN E c Ye tC AA LT 54 Pu Py Py P S a l The vari
6. the specialized ideal do not specialize to the polynomials of its own basis B These last vertices were not considered singular in MaMo05 producing some erroneous discussions as has been noticed by Wibmer Wi06 but must necessarily be considered so The rest of terminal vertices gi v descendent from v whose lpp sets are equal to that of vertex g v are non singular vertices The minimal singular variety V relative to v as the minimal variety containing all the singular specifications X V U Xs z U MCN coy N U V w L w W v The absolute generic vertex and basis as the generic vertex and GRGB relative to the root vertex The discriminant ideal J relative to vertex v by Jy N Nso where N y are the null condition ideals of the specifications corresponding to the singular vertices relative to vertex v Note that the absolute generic basis is equal to the reduced Gr bner basis of J computed in K a z by the ordinary Buchberger algorithm conveniently normalized to eliminate denominators In Fig 1 a simple example of the tree built by BUILDTREE is shown In the figure the Ipp sets of the terminal vertices a vertex v with label 1 0 and its associated generic g v singular s v s2 v and non singular g v vertices are illustrated Lemma 5 N C J Proof By construction the null condition ideal at any descendant vertex of v contains Ny as some null condition has been added to reach it T
7. But this is simpler than computing the radical Note also that properties ii iii and iv of the definition in MaMo05 are simple consequences of Definition 1 Nevertheless property iii of Definition 1 is stronger and REDSPEC denoted CANSPEC in previous papers must be designed to realize this new definition of reduced specification If property iii is not held by the concrete used REDSPEC algorithm then Theorem 3 will not be true and the algorithm DISPGB will not always built up the best tree We shall discuss this later We assume now that the algorithm BUILDTREE uses the adequate REDSPEC algo rithm and when applied to the ideal J builds up a rooted binary tree with the following properties 1 At each vertex v a dichotomic decision is taken about the vanishing or not of some polynomial p a K a 2 A vertex is labelled by a list of zeroes and ones whose root label is empty At the null son vertex p is assumed null and a zero is appended to the father s label whereas p is assumed non null at the non null son vertex in which a 1 is appended to father s label 3 At each vertex v the tree stores X and By where X Ny Wo is a reduced specification of specializations summarizing all the decisions taken in the preceding vertices starting from the root By Definition 1 it represents all the specializations with a X V Nv U ew V w B is reduced wrt X not faithful in the sense of Weispfennin
8. Canonical discussion of polynomial systems with parameters ANTONIO MONTES MA2 IR 06 00006 1 There are many authors Be94 BeWe93 De99 Du95 FoGiTr01 Gi87 Gom02 GoRe93 GoTrZa00 GoTrZa05 HeMcKa97 Ka97 Kap95 MaMo05 Mo02 Mor97 Pe94 SaSu03 SaSuNa03 Sc91 192 We92 We03 that have studied the problem of specializing parametric ideals into a field and determining the specialized Gr bner bases Many other authors Co04 Em99 GoRe93 GuOr04 Mo95 Mo98 Ry00 have applied some of these methods to solve Caninical discussion of polynomial systems with parameters Antonio Montes Departament de Matematica Aplicada 2 Universitat Polit cnica de Catalunya Spain e mail antonio montesQupc edu http www ma2 upc edu montes April 2006 Abstract Given a parametric polynomial ideal J the algorithm DISPGB introduced by the author in 2002 builds up a binary tree describing a dichotomic discussion of the different reduced Gr bner bases depending on the values of the parameters An improvement using a discriminant ideal to rewrite the tree was described by Manubens and the author in 2005 In this paper we describe how to iterate the use of discriminants to rebuild the tree and show that this leads to an ascending discriminant chain of ideals and to the corresponding descending chain of varieties in the parameter space that characterizes the different kinds of solutions This provides a discussion of the ideal J into canonica
9. S the ideals that are also in T END Table 2 CANPERFSPEC algorithm in the form Yor V C Ni V 05 M where the ideals Ny Mj are prime relative to K but can be reducible wrt K and each Mj strictly contains some Ny Mj 2 Nrg Proof By construction CANPERFSPEC produces the minimal decomposition with the required conditions Oo In the iterative rewriting process two kinds of vertices of the rewritten trees become important from here on let us denote the vertices labelled by the all zero vector 0 0 by the number n of zeroes and the vertices of the form 0 Ex 0 1 by n With this notation the root vertex becomes vertex 0 The top discriminant ideal is now Jo f N oj and by Theorem 6 V Jo is the minimal singular variety of the root vertex The first step of REBUILDTREE already described in MaMo05 consists of the fol lowing 1 put at the top vertex the decision about the discriminant Jo 2 hang at the non null branch the generic basis Bo 9 T REBUILDTREE T n Input T the tree built by BUILDTREE or by REBUILDTREE T n 1 n integer denoting the recursion level initially 0 Output T the new rebuilt tree T BEGIN REPEAT T copy T from the root cutting after vertex 0 ue 0 Ja null condition ideal of vertex 0 0 of T initially empty Ug generic terminal vertex 0 n 0 1 1 relative to 0 AA 0 of T spc SPECCASES n J N
10. V c z v V a 1 V a 1 5 U V a 1 c z z y4zrz z V b V b c U V a b y yaz azz tyry y V c V b c U V a c y aan yayta V b c V V a b c az z y V a y Even the case with GRGB y that appears divided in two subcases in trees 1 and 2 but is summarized in one single case in the third tree have the same representation after using CANPERFSPEC to add them This illustrates well the canonical character of the discussion built up by DISPGB 6 Acknowledgements I would like to thank Drs Pelegr Viader and Julian Pfeifle for their many helpful comments and his insightful perusal of our first draft I also thank my Ph D student M Manubens for helping in all the discussions and implementation details I am indebted to M Wib mer for his interesting counter example that lead me to correct the definition of singular specifications 16 References Be94 T Becker On Gr bner bases under specialization Appl Algebra Engrg Comm Comput 1994 1 8 BeWe93 T Becker V Weispfenning Gr bner Bases A Computational Approach to Commutative Algebra Springer New York 1993 Co04 M Coste Classifying serial manipulators Computer Algebra and geometric insight Plenary talk Personal communication Proceedings of EACA 2004 2004 323 323 De99 S Delli re Triangularisation de syst mes constructibles Application l valuation dynamique Th se D
11. Weispfenning s algorithm was neither very efficient nor canonical Using his suggestions the author Mo02 obtained a more efficient algorithm DISPGB for Discussing Parametric Gr bner Bases DISPGB builds up a dichotomic binary tree whose branches at each vertex correspond to the annihilation or not of a polynomial in K a It places at each vertex v a specification Ny Wy of the included specializations that summarizes the null and non null decisions taken before reaching v and a specialized basis B of og I for the specializations og Ny At the terminal vertices the basis specializes to the Gr bner basis of the specialized ideal oz 1 that has a set of leading power products lpp set which is commom to all specializations in X Inspired by DISPGB Weispfenning We03 was able to give a constructive method for obtaining a Canonical Comprehensive Gr bner Basis CCGB for parametric polynomial ideals The algorithm is based on the direct computation of a discriminant ideal Neverthe less his method is of high computational complexity and does not provide a true partition of the different cases of the parametric Gr bner system Using Weispfenning s idea of discrim inant ideal Manubens and Montes drastically improved DISPGB In MaMo05 we showed that the tree 7 1 built up by DISPGB algorithm can be rewritten into a new form T providing a more compact and effective discussion by computing a discriminant ideal that is easy to compu
12. and define the ideal J a K a ag T d4 1 deg Kg Y Then Weispfenning s discriminant We03 is the radical of the intersection Jw 4 f1gea Jg A specialization is said to be essential for J gt z if Jg C ker c for some g G Theorem 7 Consider the root vertex and its associated absolute generic case Then i A specialization is essential if and only if it is singular ii The radical of our top discriminant ideal is equal to Weispfenning s top discriminant Proof i If o is essential then it exists g G such that J C ker c Thus o f 0 for all f Jg Let hgg be the polynomial in J that corresponds to g Thus hg Ic hgq Then hg Jy C ker c and o h 0 Thus g does not specialize to a polynomial with the same lpp wrt gt y Thus G does not specialize to a basis with the same lpp set Thus c is special as either o G is a Gr bner basis of c I and then it does not have the same lpp set as G either it does not specialize to the reduced Gr bner basis of c I In both cases c is singular The argument can be reversed to prove that singular specializations are essential This proves the strong formulation of the conjecture in MaMo05 ii This constitutes the weak formulation of the conjecture and is a consequence of the strong formulation as proved in MaMo05 3 Iterative Rewriting of the Tree Using Discriminant Ideals The design of the algorithms described in MaMo05 uses ra
13. be iterated now starting from vertex 1 and in general from ver tex n until the complete rewriting process has been finished T he iterated REBUILDTREE algorithm is shown in Table 3 and the routine SPECCASES used by it to determine the special cases hanging from vertex n of the n 1 rebuilt tree is shown in Table 4 As it can be seen in SPECCASES routine we need to use a quotient of ideals similar to that used to determine Weispfenning s discriminant The whole rewrite process should now be clear At the second rebuild the discriminant J will be computed and set as decision in vertex 1 0 Thus the specification at the new vertex 2 0 1 will be X5 Jo J1 which is clearly a perfect specification and at vertex 2 0 0 it will be 32 J 1 which is also a perfect specification The complete rebuilt tree 7 will thus have the vertices and specifications given in Fi gure 2 11 Ei 0 Jo Ji X1 Jo 1 pa v 5 Jo Ji Jo X5 ji 1 v Eh A Ja Jz X3 Ja 1 i Y Ja D z5 5 35 1 z Eiariy 7 Ja 1 Ja Dgr Ja 0 Figure 2 Discriminants and Specifications in the rebuilt tree The discriminant ideals J and the associated varieties verify the inclusions 0 Jo sh Ja 4 1 1 K 2 V Jo 2 V1 2 V J2 2 2 VJ 2 6 and the set of values of the parameters corresponding to the specification of the terminal vertices i 1
14. dical null ideals as well as a radical discriminant ideal for the first rewrite of the initial tree T_1 I gt z gt za The actual design does not use necessary radicals but instead the reduced specifications verify Theorem 3 In order to rewrite the tree we need a new kind of specification of specializations Definition 8 X N M is a perfect specification of specializations if i N gb N gt a ii M gb M gt a iii N M We call Ys the algebraic set V N VN V M C K specified by X The set Ys corres ponding to a perfect specification can be described in a canonical form using the algorithm CANPERFSPEC of Table 2 as states the following Theorem 9 Given two ideals N G M the algorithm CANPERFSPEC given in Table 2 generates a unique canonical description of Ysy V N NV M c K S PRIMEDECOMP N Input N ideal representing a variety Output S The set of prime ideals of the decomposition of VN S T CANPERFSPEC N M Input N the null condition ideal of the perfect specification M the non null condition ideal of the perfect specification M D gt N Output S T The sets of prime ideals corresponding to the minimal null and non null conditions of the canonical description BEGIN M M WN S PRIMEDECOMP N T PRIMEDECOMP M Eliminate from S the ideals that are also in T Replace each ideal T in the decomposition of T by Sk T Tu ar PRIMEDECOMP T Eliminate from
15. e non canonical BUILDTREE can destroy misstand the canonical character of the rebuilding process To reach the generic case of a vertex in BUILDTREE only compatible non null decisions have been taken in the sense of reduced specifications Thus the dimension of the Zariski closure of the generic case must be equal to that of V Jo If dim V J4 lt dim V Jo then the generic basis of case 1 is also canonical as it corre sponds to the unique specification under vertex 1 whose Zariski closure has dimension equal to dim V Jo and thus does not depend on the particular tree built up by BUILDTREE The algorithm continues working so and whenever dim V J lt dim V Ji_1 the choice of the generic basis associated to vertex i does not depend on the algorithm If dim V J lt dim V Jj 1 happens for all i then the discussion tree will be absolutely canonical too Nevertheless it can happen that for some i dim V J 1 dim V J In this case V J is formed by a subset of the irreducible components of V J 1 some of them having the same dimension as the correspondent in V J 41 In this case a different possible choice of the generic case is possible and this would produce a new choice J with V J7 in V J 1 V V Ji This will produce an inversion in the order of the cases inside V J _1 Thus the discussion tree is not absolutely canonical and can produce minor predictable changes in the order of the discussion This will become clear
16. eties verify V Jo 2 V J1 2 V J2 2 V Ja cf Figure 3 The corresponding lpp sets of the reduced Gr bner bases of the Y s are all different and are summarized in the following table Specification C3 Vo Vo Vi Vi V2 Ve V3 V3 lpp sets x y z H v lev Yl Vo is a surface dimension 2 It contains V4 consisting of the six straight lines r1 rg V5 consists of two of these lines rg Ure Finally V3 consists of the four points P P4 that are the intersection of V gt rg U re and Vj ri Ur2U r3 U r4 In this case an alternative discriminant chain is possible with Vj Vo Vi Vi Vj Vi V Vo V3 V3 for which the positions 2 and 3 will be permuted being the unique change in the tree This situation can occur in a generalized situation Suppose that in a problem we have a variety V Uj_ where the V s have the same dimension and V V W for every iz j and dim W lt dim V Suppose that the problem admits the chain v2lJu2lJvi2 2W2w i 2 1 3 14 Figure 3 Varieties of the discriminant chain The specializations of the different cases that will determine CANPERFSPEC will be V W and they are independent of the order in which the embedded varieties are chosen by a strategy in DISPGB Each order of the V s is then possible for the tree but the description of the cases is canonical and independent of the order in the tree 5 2 Example 2 In order to ill
17. g and specializes to a basis of ez I for every a X 4 At the terminal vertices v B specializes to the reduced Gr bner basis of ez I for every X and has the same lpp set We will denote such a basis GRGB X Generic Reduced Gr bner Basis relative to X The specifications of the set of terminal vertices t represent subsets X C K forming a partition of the whole parameter space K X Xn Xi Xy h and the sets X have characteristic lpp sets that do not depend on the algorithm not null null z y x z y x z y x z y x yx P yx x Of yx yx yx gv s v1 9g v1 s v2 1 yx zx x Figure 1 Vertices associated to a vertex v in BUILDTREE Illustration of Definitions 4 in an example I x cy bz a cz y az b br ay z o Definition 4 Let T_1 I gt z gt a be the tree built up by BUILDTREE and v be any vertex Associated to v define i ii iii iv v The generic vertex relative to v as the terminal vertex g v descendent from v for which only non null decisions have been taken and correspondingly the generic basis specification and set of lpp s relative to v The singular vertices relatives to v as the terminal vertices s v descendent from v whose lpp sets are different from that of vertex g v as well as those terminal vertices having the same lpp set as B w GRGB X but for which the polynomi als of B j normalized to be polynomials of
18. he unique descendant terminal vertex having a null condition ideal equal to N is the generic vertex g v All the singular terminal vertices have null condition ideals that strictly contain N Thus their intersection also contains Ny o Theorem 6 Let T I gt z gt a be the tree built up by BUILDTREE and v be any vertex Then i the minimal singular variety V is Vy V Jo i JJ N ker oz ou is singular relative to vertex v Proof i Set Z U V w By Theorem 3 w Wi v U Xs U VN SQ N Zi E U VN i N Zi j i UVic T AN Nsi v V J Vo ii As K is algebraically closed I V J V Jy by the Nullstellensatz Now f VJe N V Ns v if and only if for all a LU Xx is oa f 0 which is equivalent to fe N ker oz og is singular relative to vertex v C Note that if REDSPEC does not produce exactly a reduced specification then Theo rem 6 does not apply and V J will include the minimal singular variety V but can be strictly greater In this case unnecessary non singular cases can remain inside the variety V J In MaMo05 we enunciate two forms of a conjecture that with the new definition of special cases becomes now a theorem We proof it now Remember the definitions leading to the top Weispfenning s discriminant Let G be the generic Gr bner basis of the ideal J computed in K a z Associated to each g G let dg be the lcm of the denominators of g
19. l cases even if the tree is not completely canonical It can also be used to obtain a canonical comprehensive Grobner basis With the new algorithm we realize in some sense the objective proposed by Weispfenning in 1992 We also prove the conjectures formulated in the previous paper Keywords minimal singular variety canonical discussion perfect specification ascending discriminant chain discriminant ideal comprehensive Gr bner basis parametric polynomial system MSC 68W30 13P10 13F10 Introduction Work partially supported by the Ministerio de Ciencia y Tecnolog a under project BFM2003 00368 and by the Generalitat de Catalunya under project 2005 SGR 00692 concrete problems In the previous paper M002 we give more details of their contributions to the field In the following we only refer to the papers directly related to the present work Let I C K a x be a parametric ideal in the variables x z 2 and the parameters T j m and gt and gt g monomial orders in variables and parameters respectively Weispfenning We92 proved the existence of a Comprehensive Gr bner Basis CGB of I and gave an algorithm for computing it Let K be a computable field for example Q and K an algebraically closed extension for example C A CGB is a basis of I that specializes to a Gr bner basis of ez I for any specialization oz K a x K z that substitutes the parameters by concrete values a K Nevertheless
20. octorale Universit de Limoges Limoges 1995 Du95 D Duval valuation dynamique et cl ture alg brique en Axiom Journal of Pure and Applied Algebra 99 1995 267 295 Em99 I Z Emiris Computer Algebra Methods for Studying and Computing Molecular Conformations Algorithmica 25 1999 372 402 FoGiTr01 E Fortuna P Gianni and B Trager Degree reduction under specialization Jour Pure and Applied Algebra 164 1 2 2001 153 164 Proceedings of MEGA 2000 Gi87 P Gianni Properties of Gr bner bases under specializations In EUROCAL 87 Ed J H Davenport Springer LCNS 378 1987 293 297 Gom02 T G mez D az Dynamic Constructible Closure Proceedings of Posso Workshop on Software Paris 2000 73 93 GoRe93 M J Gonz lez L pez T Recio The ROMIN inverse geometric model and the dynamic evaluation method In Computer Algebra in Industry Ed A M Cohen Wiley amp Sons 1993 117 141 GoTrZa00 M J Gonz lez L pez L Gonz lez Vega C Traverso A Zanoni Gr bner Bases Specialization through Hilbert Functions The Homogeneoas Case SIGSAM BULL Issue 131 34 1 2000 1 8 GoTrZa05 L Gonz lez Vega C Traverso A Zanoni Hilbert Stratification and Paramet ric Gr bner Bases Proceedings od CASC 2005 2005 220 235 GuOr04 M de Guzm n D Orden Finding tensegrity structures geometric and symbolic aproaches Proceedings of EACA 2004 2004 167 172 HeMcKa97 P Van Hentenryck D McAlle
21. ollowing Definition 1 X N W is a reduced specification of specializations if i N gb N gt a ii W is a set of distinct irreducible polynomials over K iii No irreducible component of V N C K is contained in U V w wcW We call Xs the semi algebraic set specified by X xsv U vw e x wcW Lemma 2 Let K be an infinite field and V W be varieties of K Then if V is irreducible and W GV then V W V Proof C V W is the minimal variety containing V V W and V is a variety containing V V W Thus VV W C V We have V WU V W CWUV W As V is irreducible then either V C W or V CV W But V C W contradicts the hypothesis thus V C VV W IU oO Using the definition of reduced specification we can now prove the following Theorem 3 Let X N W be a reduced specification of specializations Z LJ ew V w and Xs V N Z Then the Zariski closure of X is X V N 1 Available on the web Definition 7 in MaMo05 Proof Decompose V N into irreducibles V N d oam Vi We have V N Z UR Vi Z UTZ Um ZAV If no V C Z then Z n Vj s V and thus by Lemma 2 V ZAV V and finally V N VZ 2 Uta Vi V o Note that in contrast to the definition in MaMo05 we do not require N to be radical When we need to test whether a polynomial in Ka vanishes as a consequence of X it will not be sufficient to divide it by N but we will need to test if it belongs to N
22. ster and D Kapur Solving polynomial systems using a branch and prune approach SIAM J Numer Anal 34 2 1997 797 827 Ka97 M Kalkbrenner On the stability of Gr bner bases under specializations Jour Symb Comp 24 1 1997 51 58 17 Kap95 D Kapur An Approach for Solving Systems of Parametric Polynomial Equations In Principles and Practices of Constraints Programming Ed Saraswat and Van Hentenryck MIT Press 1995 217 244 MaMo05 M Manubens A Montes Improving DISPGB Algorithm Using the Discrim inant Ideal Short abstract in Proceedings of Algorithmic Algebra and Logic 2005 159 166 arXiv math AC 0601763 To be published in Jour Symb Comp Mo95 A Montes Solving the load flow problem using Gr bner bases SIGSAM Bull 29 1995 1 13 Mo98 A Montes Algebraic solution of the load flow problem for a 4 nodes electrical network Math and Comp in Simul 45 1998 163 174 Mo02 A Montes New algorithm for discussing Gr bner bases with parameters Jour Symb Comp 33 1 2 2002 183 208 Mor97 M Moreno Maza Calculs de Pgcd au dessus des Tours d xtensions Simples et R solution des Syst mes d Equatoins Algebriques Doctoral Thesis Universit Paris 6 1997 Pe94 M Pesh Computing Comprehesive Gr bner Bases using MAS User Manual Sept 1994 Ry00 M Rychlik Complexity and Applications of Parametric Algorithms of Computa tional Algebraic Geometry In Dynamics of Algorithms
23. te from 7T We proved that our discriminant contains Weispfenning dis criminant ideal and we conjectured the equality A redefinition of the discriminant allows now to prove the conjecture The old DISPGB is renamed BUILDTREE as it builds up the first discussion tree T_1 and a new algorithm REBUILDTREE is added to rewrite the tree and both are included in the new DISPGB algorithm outlined in Table 1 The main contribution of this paper is the iteration of the rewrite process to deeper levels Some theoretical problems remained open for this In this paper all these problems are solved proving that the iteration of REBUILDTREE to each level produces an ascending chain of discriminant ideals J1 0 G Jo amp JA G Jk G Kla Jia and the corresponding descending chain of minimal varieties K 2V J 2V A 2 2 Ve 20 in the parameter space K A descending chain determines a partition YT Yo Yi Yk T DISPGB B gt z gt a Input B C R a z basis of T zu term orders wrt the variables x and the parameters a respectively Output T table with binary tree structure containing Gy 35 at vertex v BEGIN T_ BUILDTREE B lt z lt a T REBUILDTREE T_1 0 END Table 1 DISPGB algorithm of K into the sets Y V Jj_1 V J C K for which the basis G C K a z provided by the algorithm has a characteristic lpp set 2 and specializes to the reduced Gr bner basis of ea I for
24. ustrate distinct possible alternatives for the discussion tree consider the fol lowing ideal with three parameters I abe x y z be a y yz ac zy y ab ryt z arz y Take monomial orders lex x y z and lex a b c Depending on the strategy in DISPGB we obtain three different trees that can be seen in Figure 4 and the correponding ascending discriminant chains Tree 1 a l abe amp abc amp 0000 C abac bc G a be Tree 2 a 1 abc G abc ab ab ac bc G a b Tree 3 a 1 abc abc ac G abac amp a Nevertheless as we have discussed in previous section using CANPERFSPEC all the chains lead to the same canonical specification and generic reduced Gr bner bases of the cases shown in the next table 15 not null a b c a 2 b c null notnull a b c a 2 b c null abo m a b d z y MEME z y ms E b c LEE a b z 2 y x z uem 2 2 y x z pss scu b c a c pue ae a c a b D _ ae ae b c a t a b c b y 3 243 x x y2 oe y 8 z 3 x x y 2 ee c b c a EN S c D a y 2 z 8 x x y n L y MM ee 20x ly psg ly not null a b cra 2 b c null Ja b c z y u sc a a c z 2 y x z ol uem PER M a c a b y 8 z 8 x x y 2 nm Eve n n 8l y 2 z 3 x x y ME p ly Figure 4 Discussion trees 1 2 3 in example 2 Specification Reduced Gr bner Basis C3 V a U V a 1 U V b U
25. ut n integer denoting the recursion level initially 0 Output Spc the special cases descending from vertex n of T BEGIN c Set of terminal vertices descending from vertex n c Select from c the cases with Ipp B 4 Ipp By CQ IF c Z c4 THEN FOR g By DO hg lc ag with ag oy 1 FOR ALL t CVG DO test true FOR ALL g By WHILE test DO IF c hj 0 THEN test false IF test THEN c2 c2 U ti Spc c1 N C2 END Table 4 SPECCASES routine called inside REBUILDTREE After the first rebuild the specification at the new vertex 1 is U4 Jo 1 and cor responds to the root vertex of the old tree T_ That specification represents the subset of values of the specializations included Yo V Jo for which Bo is the GRGB The non null branch will summarize the largest set of generic specifications of T 1 given by a perfect specialization that were before under the null branch Most of the non special cases of the old tree will be included now in the new enlarged generic specification and correspondingly will become incompatible and disappear under the null branch in the new tree when adding the discriminant condition The new specifications under the null branch will continue to verify Theorems 3 6 The old singular cases at the terminal vertices will neither disappear nor change because these null conditions already contain the new discriminant condition The rewrite process can
26. w the singular cases include all the cases to which the generic Gr bner basis does not specialize to a Gr bner basis of the case even if both basis have the same lpp sets With this modification the discussion becomes correct and we can also prove the equality of Weispfenning and our top discriminant ideals The algorithm works with ideals as these are the algebraic objects that allow a Gr bner representation Nevertheless as it does not always use radical ideals ideals do not represent varieties in a unique form So to prove our results we adopt frequently a geometrical view about the specifications of specializations considering the corresponding varieties This leads to slightly different definitions and properties than those given in MaMo05 The canonical Grobner system so obtained allows to compute also a canonical compre hensive Gr bner basis completing the objective of Weispfenning in We92 Manubens and Montes have implemented the new algorithm in Maple in release 4 1 of DPGB 2 Reviewing BUILDTREE BUILDTREE is described in MaMo05 and improves the original DISPGB described in Mo02 So it will not be described hereafter Nevertheless we need to replace the concept of reduced specification of specializations X N W used inside BUILDTREE Remember that N represents the null conditions and W the non null conditions To attain now the geometrical perspective the definition given in MaMo05 must be substituted by the f
27. way than the discussion is described in a complete canonical form Even when REBUILDTREE is not able to summarize every generic reduced Gr bner basis into a single case we can use CANPERFSPEC in an external routine applied to the final tree to achieve the unification of cases So it is always possible to obtain a canonical representation of the different specialization cases Nevertheless the order in which the different cases appear in the tree is still algorithm depending to some extent Let us comment this point The absolute generic basis B g does not depend on the algorithm and so the same is true for the set U X 9 Ui X 0 Thus V Jo is canonical The first step of REBUILDTREE algorithm then rewrites the tree setting as new generic case the perfect specification given by K XV V Jo that is thus not algorithm depending All the special cases remain under the null branch of the new top decision At the new step of REBUILDTREE the new generic basis B relative to the new vertex 1 for which only non null conditions have been added is chosen and the new discriminant J D Jo is determined So the new perfect specification X Jo J1 is obtained for the new generic vertex relative to the new vertex 1 that we denote 1 It corresponds to the set of parameter values V Jo V V J1 Only the possibility of a different choice of the basis for the new generic case relative to vertex 1 that can appear in a different tree obtained by th
Download Pdf Manuals
Related Search