==================================================================== Lex Triangular Package ==================================================================== The LexTriangularPackage package constructor provides an implementation of the lexTriangular algorithm [Lazard]_. This algorithm decomposes a zero-dimensional variety into zero-sets of regular triangular sets. Thus the input system must have a finite number of complex solutions. Moreover, this system needs to be a lexicographical Groebner basis. This package takes two arguments: the coefficient-ring R of the polynomials, which must be a GcdDomain and their set of variables given by ls a List Symbol. The type of the input polynomials must be NewSparseMultivariatePolynomial(R,V) where V is OrderedVariableList(ls). The abbreviation for LexTriangularPackage is LEXTRIPK. The main operations are lexTriangular and squareFreeLexTriangular. The later provide decompositions by means of square-free regular triangular sets, built with the SquareFreeRegularTriangularSet constructor, whereas the former uses the RegularTriangularSet constructor. Note that these constructors also implement another algorithm for solving algebraic systems by means of regular triangular sets; in that case no computations of Groebner bases are needed and the input system may have any dimension (i.e. it may have an infinite number of solutions). The implementation of the lexTriangular algorithm provided in the LexTriangularPackage constructor differs from that reported in "Computations of gcd over algebraic towers of simple extensions" by M. Moreno Maza and R. Rioboo (in proceedings of AAECC11, Paris, 1995). Indeed, the squareFreeLexTriangular operation removes all multiplicities of the solutions (i.e. the computed solutions are pairwise different) and the lexTriangular operation may keep some multiplicities; this later operation runs generally faster than the former. The interest of the lexTriangular algorithm is due to the following experimental remark. For some examples, a triangular decomposition of a zero-dimensional variety can be computed faster via a lexicographical Groebner basis computation than by using a direct method (like that of SquareFreeRegularTriangularSet and RegularTriangularSet). This happens typically when the total degree of the system relies essentially on its smallest variable (like in the Katsura systems). When this is not the case, the direct method may give better timings (like in the Rose system). Of course, the direct method can also be applied to a lexicographical Groebner basis. However, the lexTriangular algorithm takes advantage of the structure of this basis and avoids many unnecessary computations which are performed by the direct method. For this purpose of solving algebraic systems with a finite number of solutions, see also the ZeroDimensionalSolvePackage. It allows to use both strategies (the lexTriangular algorithm and the direct method) for computing either the complex or real roots of a system. Note that the way of understanding triangular decompositions is detailed in the example of the RegularTriangularSet constructor. Since the LexTriangularPackage package constructor is limited to zero-dimensional systems, it provides a zeroDimensional? operation to check whether this requirement holds. There is also a groebner operation to compute the lexicographical Groebner basis of a set of polynomials with type NewSparseMultivariatePolynomial(R,V). The elimination ordering is that given by ls (the greatest variable being the first element of ls). This basis is computed by the FLGM algorithm [Faugere]_ implemented in the LinGroebnerPackage package constructor. Once a lexicographical Groebner basis is computed, then one can call the operations lexTriangular and squareFreeLexTriangular. Note that these operations admit an optional argument to produce normalized triangular sets. There is also a zeroSetSplit operation which does all the job from the input system; an error is produced if this system is not zero-dimensional. Let us illustrate the facilities of the LexTriangularPackage constructor by a famous example, the cyclic-6 root system. Define the coefficient ring. :: R := Integer Integer Type: Domain Define the list of variables, :: ls : List Symbol := [a,b,c,d,e,f] [a,b,c,d,e,f] Type: List Symbol and make it an ordered set. :: V := OVAR(ls) OrderedVariableList [a,b,c,d,e,f] Type: Domain Define the polynomial ring. :: P := NSMP(R, V) NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f]) Type: Domain Define the polynomials. :: p1: P := a*b*c*d*e*f - 1 f e d c b a - 1 Type: NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) p2: P := a*b*c*d*e +a*b*c*d*f +a*b*c*e*f +a*b*d*e*f +a*c*d*e*f +b*c*d*e*f ((((e + f)d + f e)c + f e d)b + f e d c)a + f e d c b Type: NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) p3: P := a*b*c*d + a*b*c*f + a*b*e*f + a*d*e*f + b*c*d*e + c*d*e*f (((d + f)c + f e)b + f e d)a + e d c b + f e d c Type: NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) p4: P := a*b*c + a*b*f + a*e*f + b*c*d + c*d*e + d*e*f ((c + f)b + f e)a + d c b + e d c + f e d Type: NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) p5: P := a*b + a*f + b*c + c*d + d*e + e*f (b + f)a + c b + d c + e d + f e Type: NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) p6: P := a + b + c + d + e + f a + b + c + d + e + f Type: NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) lp := [p1, p2, p3, p4, p5, p6] [f e d c b a - 1, ((((e + f)d + f e)c + f e d)b + f e d c)a + f e d c b, (((d + f)c + f e)b + f e d)a + e d c b + f e d c, ((c + f)b + f e)a + d c b + e d c + f e d, (b + f)a + c b + d c + e d + f e, a + b + c + d + e + f] Type: List NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) Now call LEXTRIPK. :: lextripack := LEXTRIPK(R,ls) LexTriangularPackage(Integer,[a,b,c,d,e,f]) Type: Domain Compute the lexicographical Groebner basis of the system. This may take between 5 minutes and one hour, depending on your machine. :: lg := groebner(lp)$lextripack [a + b + c + d + e + f, 2 2 3968379498283200b + 15873517993132800f b + 3968379498283200d + ... ... **OUPUT CUT** ... 26 20 14 - 12090487758628245f - 8787672733575f + 12083693383005045f + 8 2 9672870290826025f + 68544102808525f , 48 42 36 30 18 12 6 f - 2554f - 399710f - 499722f + 499722f + 399710f + 2554f - 1] Type: List NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) Apply lexTriangular to compute a decomposition into regular triangular sets. This should not take more than 5 seconds. :: lexTriangular(lg,false)$lextripack [ 6 6 5 2 4 3 3 4 2 5 {f + 1, e - 3f e + 3f e - 4f e + 3f e - 3f e - 1, 2 5 3 4 4 3 5 2 3d + f e - 4f e + 4f e - 2f e - 2e + 2f, c + f, 2 5 3 4 4 3 5 2 3b + 2f e - 5f e + 5f e - 10f e - 4e + 7f, 2 5 3 4 4 3 5 2 a - f e + 3f e - 3f e + 4f e + 3e - 3f} , 6 2 2 2 {f - 1,e - f,d - f,c + 4f c + f ,(c - f)b - f c - 5f ,a + b + c + 3f}, 6 2 2 {f - 1,e - f,d - f,c - f,b + 4f b + f ,a + b + 4f}, 6 2 2 2 {f - 1,e - f,d + 4f d + f ,(d - f)c - f d - 5f ,b - f,a + c + d + 3f}, 36 30 24 18 12 6 {f - 2554f - 399709f - 502276f - 399709f - 2554f + 1, 12 2 (161718564f - 161718564)e + 31 25 19 13 - 504205f + 1287737951f + 201539391380f + 253982817368f + 7 201940704665f + 1574134601f * e + 32 26 20 14 - 2818405f + 7198203911f + 1126548149060f + 1416530563364f + 8 2 1127377589345f + 7988820725f , 6 2 5 3 4 (693772639560f - 693772639560)d - 462515093040f e + 1850060372160f e + 4 3 11 5 2 - 1850060372160f e + (- 24513299931120f - 23588269745040f )e + 30 24 18 - 890810428f + 2275181044754f + 355937263869776f + 12 6 413736880104344f + 342849304487996f + 3704966481878 * e + 31 25 19 - 4163798003f + 10634395752169f + 1664161760192806f + 13 7 2079424391370694f + 1668153650635921f + 10924274392693f , 6 31 25 (12614047992f - 12614047992)c - 7246825f + 18508536599f + 19 13 7 2896249516034f + 3581539649666f + 2796477571739f - 48094301893f , 6 2 5 3 4 (693772639560f - 693772639560)b - 925030186080f e + 2312575465200f e + 4 3 11 5 2 - 2312575465200f e + (- 40007555547960f - 35382404617560f )e + 30 24 18 - 3781280823f + 9657492291789f + 1511158913397906f + 12 6 1837290892286154f + 1487216006594361f + 8077238712093 * e + 31 25 19 - 9736390478f + 24866827916734f + 3891495681905296f + 13 7 4872556418871424f + 3904047887269606f + 27890075838538f , a + b + c + d + e + f} , 6 2 2 2 {f - 1,e + 4f e + f ,(e - f)d - f e - 5f ,c - f,b - f,a + d + e + 3f}] Type: List RegularChain(Integer,[a,b,c,d,e,f]) Note that the first set of the decomposition is normalized (all initials are integer numbers) but not the second one (normalized triangular sets are defined in the description of the NormalizedTriangularSetCategory constructor). So apply now lexTriangular to produce normalized triangular sets. :: lts := lexTriangular(lg,true)$lextripack [ 6 6 5 2 4 3 3 4 2 5 {f + 1, e - 3f e + 3f e - 4f e + 3f e - 3f e - 1, 2 5 3 4 4 3 5 2 3d + f e - 4f e + 4f e - 2f e - 2e + 2f, c + f, 2 5 3 4 4 3 5 2 3b + 2f e - 5f e + 5f e - 10f e - 4e + 7f, 2 5 3 4 4 3 5 2 a - f e + 3f e - 3f e + 4f e + 3e - 3f} , 6 2 2 {f - 1,e - f,d - f,c + 4f c + f ,b + c + 4f,a - f}, 6 2 2 {f - 1,e - f,d - f,c - f,b + 4f b + f ,a + b + 4f}, 6 2 2 {f - 1,e - f,d + 4f d + f ,c + d + 4f,b - f,a - f}, 36 30 24 18 12 6 {f - 2554f - 399709f - 502276f - 399709f - 2554f + 1, 2 1387545279120e + 31 25 19 4321823003f - 11037922310209f - 1727506390124986f + 13 7 - 2176188913464634f - 1732620732685741f - 13506088516033f * e + 32 26 20 24177661775f - 61749727185325f - 9664082618092450f + 14 8 2 - 12152237485813570f - 9672870290826025f - 68544102808525f , 1387545279120d + 30 24 18 - 1128983050f + 2883434331830f + 451234998755840f + 12 6 562426491685760f + 447129055314890f - 165557857270 * e + 31 25 19 - 1816935351f + 4640452214013f + 726247129626942f + 13 7 912871801716798f + 726583262666877f + 4909358645961f , 31 25 19 1387545279120c + 778171189f - 1987468196267f - 310993556954378f + 13 7 - 383262822316802f - 300335488637543f + 5289595037041f , 1387545279120b + 30 24 18 1128983050f - 2883434331830f - 451234998755840f + 12 6 - 562426491685760f - 447129055314890f + 165557857270 * e + 31 25 19 - 3283058841f + 8384938292463f + 1312252817452422f + 13 7 1646579934064638f + 1306372958656407f + 4694680112151f , 31 25 1387545279120a + 1387545279120e + 4321823003f - 11037922310209f + 19 13 7 - 1727506390124986f - 2176188913464634f - 1732620732685741f + - 13506088516033f } , 6 2 2 {f - 1,e + 4f e + f ,d + e + 4f,c - f,b - f,a - f}] Type: List RegularChain(Integer,[a,b,c,d,e,f]) We check that all initials are constant. :: [ [init(p) for p in (ts :: List(P))] for ts in lts] [[1,3,1,3,1,1], [1,1,1,1,1,1], [1,1,1,1,1,1], [1,1,1,1,1,1], [1387545279120,1387545279120,1387545279120,1387545279120,1387545279120,1], [1,1,1,1,1,1]] Type: List List NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f]) Note that each triangular set in lts is a lexicographical Groebner basis. Recall that a point belongs to the variety associated with lp if and only if it belongs to that associated with one triangular set ts in lts. By running the squareFreeLexTriangular operation, we retrieve the above decomposition. :: squareFreeLexTriangular(lg,true)$lextripack [ 6 6 5 2 4 3 3 4 2 5 {f + 1, e - 3f e + 3f e - 4f e + 3f e - 3f e - 1, 2 5 3 4 4 3 5 2 3d + f e - 4f e + 4f e - 2f e - 2e + 2f, c + f, 2 5 3 4 4 3 5 2 3b + 2f e - 5f e + 5f e - 10f e - 4e + 7f, 2 5 3 4 4 3 5 2 a - f e + 3f e - 3f e + 4f e + 3e - 3f} , 6 2 2 {f - 1,e - f,d - f,c + 4f c + f ,b + c + 4f,a - f}, 6 2 2 {f - 1,e - f,d - f,c - f,b + 4f b + f ,a + b + 4f}, 6 2 2 {f - 1,e - f,d + 4f d + f ,c + d + 4f,b - f,a - f}, 36 30 24 18 12 6 {f - 2554f - 399709f - 502276f - 399709f - 2554f + 1, 2 1387545279120e + 31 25 19 4321823003f - 11037922310209f - 1727506390124986f + 13 7 - 2176188913464634f - 1732620732685741f - 13506088516033f * e + 32 26 20 24177661775f - 61749727185325f - 9664082618092450f + 14 8 2 - 12152237485813570f - 9672870290826025f - 68544102808525f , 1387545279120d + 30 24 18 - 1128983050f + 2883434331830f + 451234998755840f + 12 6 562426491685760f + 447129055314890f - 165557857270 * e + 31 25 19 - 1816935351f + 4640452214013f + 726247129626942f + 13 7 912871801716798f + 726583262666877f + 4909358645961f , 31 25 19 1387545279120c + 778171189f - 1987468196267f - 310993556954378f + 13 7 - 383262822316802f - 300335488637543f + 5289595037041f , 1387545279120b + 30 24 18 1128983050f - 2883434331830f - 451234998755840f + 12 6 - 562426491685760f - 447129055314890f + 165557857270 * e + 31 25 19 - 3283058841f + 8384938292463f + 1312252817452422f + 13 7 1646579934064638f + 1306372958656407f + 4694680112151f , 31 25 1387545279120a + 1387545279120e + 4321823003f - 11037922310209f + 19 13 7 - 1727506390124986f - 2176188913464634f - 1732620732685741f + - 13506088516033f } , 6 2 2 {f - 1,e + 4f e + f ,d + e + 4f,c - f,b - f,a - f}] Type: List SquareFreeRegularTriangularSet(Integer, IndexedExponents OrderedVariableList [a,b,c,d,e,f], OrderedVariableList [a,b,c,d,e,f], NewSparseMultivariatePolynomial(Integer, OrderedVariableList [a,b,c,d,e,f])) Thus the solutions given by lts are pairwise different. We count them as follows. :: reduce(+,[degree(ts) for ts in lts]) 156 Type: PositiveInteger We can investigate the triangular decomposition lts by using the ZeroDimensionalSolvePackage. This requires to add an extra variable (smaller than the others) as follows. :: ls2 : List Symbol := concat(ls,new()$Symbol) [a,b,c,d,e,f,%A] Type: List Symbol Then we call the package. :: zdpack := ZDSOLVE(R,ls,ls2) (20) ZeroDimensionalSolvePackage(Integer,[a,b,c,d,e,f],[a,b,c,d,e,f,%A]) Type: Domain We compute a univariate representation of the variety associated with the input system as follows. :: concat [univariateSolve(ts)$zdpack for ts in lts] [ 4 2 [complexRoots= ? - 13? + 49, coordinates = 3 3 3 3 [7a + %A - 6%A, 21b + %A + %A, 21c - 2%A + 19%A, 7d - %A + 6%A, 3 3 21e - %A - %A, 21f + 2%A - 19%A] ] , 4 2 [complexRoots= ? + 11? + 49, coordinates = 3 3 3 [35a + 3%A + 19%A, 35b + %A + 18%A, 35c - 2%A - %A, 3 3 3 35d - 3%A - 19%A, 35e - %A - 18%A, 35f + 2%A + %A] ] , [ complexRoots = 8 7 6 5 4 3 2 ? - 12? + 58? - 120? + 207? - 360? + 802? - 1332? + 1369 , coordinates = [ 7 6 5 4 43054532a + 33782%A - 546673%A + 3127348%A - 6927123%A + 3 2 4365212%A - 25086957%A + 39582814%A - 107313172 , 7 6 5 4 43054532b - 33782%A + 546673%A - 3127348%A + 6927123%A + 3 2 - 4365212%A + 25086957%A - 39582814%A + 107313172 , 7 6 5 4 21527266c - 22306%A + 263139%A - 1166076%A + 1821805%A + 3 2 - 2892788%A + 10322663%A - 9026596%A + 12950740 , 7 6 5 4 43054532d + 22306%A - 263139%A + 1166076%A - 1821805%A + 3 2 2892788%A - 10322663%A + 30553862%A - 12950740 , 7 6 5 4 43054532e - 22306%A + 263139%A - 1166076%A + 1821805%A + 3 2 - 2892788%A + 10322663%A - 30553862%A + 12950740 , 7 6 5 4 21527266f + 22306%A - 263139%A + 1166076%A - 1821805%A + 3 2 2892788%A - 10322663%A + 9026596%A - 12950740 ] ] , [ complexRoots = 8 7 6 5 4 3 2 ? + 12? + 58? + 120? + 207? + 360? + 802? + 1332? + 1369 , coordinates = [ 7 6 5 4 43054532a + 33782%A + 546673%A + 3127348%A + 6927123%A + 3 2 4365212%A + 25086957%A + 39582814%A + 107313172 , 7 6 5 4 43054532b - 33782%A - 546673%A - 3127348%A - 6927123%A + 3 2 - 4365212%A - 25086957%A - 39582814%A - 107313172 , 7 6 5 4 21527266c - 22306%A - 263139%A - 1166076%A - 1821805%A + 3 2 - 2892788%A - 10322663%A - 9026596%A - 12950740 , 7 6 5 4 43054532d + 22306%A + 263139%A + 1166076%A + 1821805%A + 3 2 2892788%A + 10322663%A + 30553862%A + 12950740 , 7 6 5 4 43054532e - 22306%A - 263139%A - 1166076%A - 1821805%A + 3 2 - 2892788%A - 10322663%A - 30553862%A - 12950740 , 7 6 5 4 21527266f + 22306%A + 263139%A + 1166076%A + 1821805%A + 3 2 2892788%A + 10322663%A + 9026596%A + 12950740 ] ] , 4 2 [complexRoots= ? - ? + 1, 3 3 3 3 coordinates= [a - %A,b + %A - %A,c + %A ,d + %A,e - %A + %A,f - %A ]] , 8 6 4 2 [complexRoots= ? + 4? + 12? + 16? + 4, coordinates = 7 5 3 7 5 3 [4a - 2%A - 7%A - 20%A - 22%A, 4b + 2%A + 7%A + 20%A + 22%A, 7 5 3 7 5 3 4c + %A + 3%A + 10%A + 10%A, 4d + %A + 3%A + 10%A + 6%A, 7 5 3 7 5 3 4e - %A - 3%A - 10%A - 6%A, 4f - %A - 3%A - 10%A - 10%A] ] , 4 3 2 [complexRoots= ? + 6? + 30? + 36? + 36, coordinates = 3 2 3 2 [30a - %A - 5%A - 30%A - 6, 6b + %A + 5%A + 24%A + 6, 3 2 3 2 30c - %A - 5%A - 6, 30d - %A - 5%A - 30%A - 6, 3 2 3 2 30e - %A - 5%A - 30%A - 6, 30f - %A - 5%A - 30%A - 6] ] , 4 3 2 [complexRoots= ? - 6? + 30? - 36? + 36, coordinates = 3 2 3 2 [30a - %A + 5%A - 30%A + 6, 6b + %A - 5%A + 24%A - 6, 3 2 3 2 30c - %A + 5%A + 6, 30d - %A + 5%A - 30%A + 6, 3 2 3 2 30e - %A + 5%A - 30%A + 6, 30f - %A + 5%A - 30%A + 6] ] , 2 [complexRoots= ? + 6? + 6, coordinates= [a + 1,b - %A - 5,c + %A + 1,d + 1,e + 1,f + 1]] , 2 [complexRoots= ? - 6? + 6, coordinates= [a - 1,b - %A + 5,c + %A - 1,d - 1,e - 1,f - 1]] , 4 3 2 [complexRoots= ? + 6? + 30? + 36? + 36, coordinates = 3 2 3 2 [6a + %A + 5%A + 24%A + 6, 30b - %A - 5%A - 6, 3 2 3 2 30c - %A - 5%A - 30%A - 6, 30d - %A - 5%A - 30%A - 6, 3 2 3 2 30e - %A - 5%A - 30%A - 6, 30f - %A - 5%A - 30%A - 6] ] , 4 3 2 [complexRoots= ? - 6? + 30? - 36? + 36, coordinates = 3 2 3 2 [6a + %A - 5%A + 24%A - 6, 30b - %A + 5%A + 6, 3 2 3 2 30c - %A + 5%A - 30%A + 6, 30d - %A + 5%A - 30%A + 6, 3 2 3 2 30e - %A + 5%A - 30%A + 6, 30f - %A + 5%A - 30%A + 6] ] , 2 [complexRoots= ? + 6? + 6, coordinates= [a - %A - 5,b + %A + 1,c + 1,d + 1,e + 1,f + 1]] , 2 [complexRoots= ? - 6? + 6, coordinates= [a - %A + 5,b + %A - 1,c - 1,d - 1,e - 1,f - 1]] , 4 3 2 [complexRoots= ? + 6? + 30? + 36? + 36, coordinates = 3 2 3 2 [30a - %A - 5%A - 30%A - 6, 30b - %A - 5%A - 30%A - 6, 3 2 3 2 6c + %A + 5%A + 24%A + 6, 30d - %A - 5%A - 6, 3 2 3 2 30e - %A - 5%A - 30%A - 6, 30f - %A - 5%A - 30%A - 6] ] , 4 3 2 [complexRoots= ? - 6? + 30? - 36? + 36, coordinates = 3 2 3 2 [30a - %A + 5%A - 30%A + 6, 30b - %A + 5%A - 30%A + 6, 3 2 3 2 6c + %A - 5%A + 24%A - 6, 30d - %A + 5%A + 6, 3 2 3 2 30e - %A + 5%A - 30%A + 6, 30f - %A + 5%A - 30%A + 6] ] , 2 [complexRoots= ? + 6? + 6, coordinates= [a + 1,b + 1,c - %A - 5,d + %A + 1,e + 1,f + 1]] , 2 [complexRoots= ? - 6? + 6, coordinates= [a - 1,b - 1,c - %A + 5,d + %A - 1,e - 1,f - 1]] , 8 7 6 5 4 2 [complexRoots= ? + 6? + 16? + 24? + 18? - 8? + 4, coordinates = 7 6 5 4 3 2 [2a + 2%A + 9%A + 18%A + 19%A + 4%A - 10%A - 2%A + 4, 7 6 5 4 3 2 2b + 2%A + 9%A + 18%A + 19%A + 4%A - 10%A - 4%A + 4, 7 6 5 4 3 2c - %A - 4%A - 8%A - 9%A - 4%A - 2%A - 4, 7 6 5 4 3 2d + %A + 4%A + 8%A + 9%A + 4%A + 2%A + 4, 7 6 5 4 3 2 2e - 2%A - 9%A - 18%A - 19%A - 4%A + 10%A + 4%A - 4, 7 6 5 4 3 2 2f - 2%A - 9%A - 18%A - 19%A - 4%A + 10%A + 2%A - 4] ] , [ complexRoots = 8 7 6 5 4 3 2 ? + 12? + 64? + 192? + 432? + 768? + 1024? + 768? + 256 , coordinates = [ 7 6 5 4 3 2 1408a - 19%A - 200%A - 912%A - 2216%A - 4544%A - 6784%A + - 6976%A - 1792 , 7 6 5 4 3 2 1408b - 37%A - 408%A - 1952%A - 5024%A - 10368%A - 16768%A + - 17920%A - 5120 , 7 6 5 4 3 2 1408c + 37%A + 408%A + 1952%A + 5024%A + 10368%A + 16768%A + 17920%A + 5120 , 7 6 5 4 3 2 1408d + 19%A + 200%A + 912%A + 2216%A + 4544%A + 6784%A + 6976%A + 1792 , 2e + %A, 2f - %A] ] , 8 6 4 2 [complexRoots= ? + 4? + 12? + 16? + 4, coordinates = 7 5 3 7 5 3 [4a - %A - 3%A - 10%A - 6%A, 4b - %A - 3%A - 10%A - 10%A, 7 5 3 7 5 3 4c - 2%A - 7%A - 20%A - 22%A, 4d + 2%A + 7%A + 20%A + 22%A, 7 5 3 7 5 3 4e + %A + 3%A + 10%A + 10%A, 4f + %A + 3%A + 10%A + 6%A] ] , 8 6 4 2 [complexRoots= ? + 16? - 96? + 256? + 256, coordinates = 7 5 3 [512a - %A - 12%A + 176%A - 448%A, 7 5 3 128b - %A - 16%A + 96%A - 256%A, 7 5 3 128c + %A + 16%A - 96%A + 256%A, 7 5 3 512d + %A + 12%A - 176%A + 448%A, 2e + %A, 2f - %A] ] , [ complexRoots = 8 7 6 5 4 3 2 ? - 12? + 64? - 192? + 432? - 768? + 1024? - 768? + 256 , coordinates = [ 7 6 5 4 3 2 1408a - 19%A + 200%A - 912%A + 2216%A - 4544%A + 6784%A + - 6976%A + 1792 , 7 6 5 4 3 2 1408b - 37%A + 408%A - 1952%A + 5024%A - 10368%A + 16768%A + - 17920%A + 5120 , 7 6 5 4 3 2 1408c + 37%A - 408%A + 1952%A - 5024%A + 10368%A - 16768%A + 17920%A - 5120 , 7 6 5 4 3 2 1408d + 19%A - 200%A + 912%A - 2216%A + 4544%A - 6784%A + 6976%A - 1792 , 2e + %A, 2f - %A] ] , 8 7 6 5 4 2 [complexRoots= ? - 6? + 16? - 24? + 18? - 8? + 4, coordinates = 7 6 5 4 3 2 [2a + 2%A - 9%A + 18%A - 19%A + 4%A + 10%A - 2%A - 4, 7 6 5 4 3 2 2b + 2%A - 9%A + 18%A - 19%A + 4%A + 10%A - 4%A - 4, 7 6 5 4 3 2c - %A + 4%A - 8%A + 9%A - 4%A - 2%A + 4, 7 6 5 4 3 2d + %A - 4%A + 8%A - 9%A + 4%A + 2%A - 4, 7 6 5 4 3 2 2e - 2%A + 9%A - 18%A + 19%A - 4%A - 10%A + 4%A + 4, 7 6 5 4 3 2 2f - 2%A + 9%A - 18%A + 19%A - 4%A - 10%A + 2%A + 4] ] , 4 2 [complexRoots= ? + 12? + 144, coordinates = 2 2 2 2 [12a - %A - 12, 12b - %A - 12, 12c - %A - 12, 12d - %A - 12, 2 2 6e + %A + 3%A + 12, 6f + %A - 3%A + 12] ] , 4 3 2 [complexRoots= ? + 6? + 30? + 36? + 36, coordinates = 3 2 3 2 [6a - %A - 5%A - 24%A - 6, 30b + %A + 5%A + 30%A + 6, 3 2 3 2 30c + %A + 5%A + 30%A + 6, 30d + %A + 5%A + 30%A + 6, 3 2 3 2 30e + %A + 5%A + 30%A + 6, 30f + %A + 5%A + 6] ] , 4 3 2 [complexRoots= ? - 6? + 30? - 36? + 36, coordinates = 3 2 3 2 [6a - %A + 5%A - 24%A + 6, 30b + %A - 5%A + 30%A - 6, 3 2 3 2 30c + %A - 5%A + 30%A - 6, 30d + %A - 5%A + 30%A - 6, 3 2 3 2 30e + %A - 5%A + 30%A - 6, 30f + %A - 5%A - 6] ] , 4 2 [complexRoots= ? + 12? + 144, coordinates = 2 2 2 2 [12a + %A + 12, 12b + %A + 12, 12c + %A + 12, 12d + %A + 12, 2 2 6e - %A + 3%A - 12, 6f - %A - 3%A - 12] ] , 2 [complexRoots= ? - 12, coordinates= [a - 1,b - 1,c - 1,d - 1,2e + %A + 4,2f - %A + 4]] , 2 [complexRoots= ? + 6? + 6, coordinates= [a + %A + 5,b - 1,c - 1,d - 1,e - 1,f - %A - 1]] , 2 [complexRoots= ? - 6? + 6, coordinates= [a + %A - 5,b + 1,c + 1,d + 1,e + 1,f - %A + 1]] , 2 [complexRoots= ? - 12, coordinates= [a + 1,b + 1,c + 1,d + 1,2e + %A - 4,2f - %A - 4]] , 4 3 2 [complexRoots= ? + 6? + 30? + 36? + 36, coordinates = 3 2 3 2 [30a - %A - 5%A - 30%A - 6, 30b - %A - 5%A - 30%A - 6, 3 2 3 2 30c - %A - 5%A - 30%A - 6, 6d + %A + 5%A + 24%A + 6, 3 2 3 2 30e - %A - 5%A - 6, 30f - %A - 5%A - 30%A - 6] ] , 4 3 2 [complexRoots= ? - 6? + 30? - 36? + 36, coordinates = 3 2 3 2 [30a - %A + 5%A - 30%A + 6, 30b - %A + 5%A - 30%A + 6, 3 2 3 2 30c - %A + 5%A - 30%A + 6, 6d + %A - 5%A + 24%A - 6, 3 2 3 2 30e - %A + 5%A + 6, 30f - %A + 5%A - 30%A + 6] ] , 2 [complexRoots= ? + 6? + 6, coordinates= [a + 1,b + 1,c + 1,d - %A - 5,e + %A + 1,f + 1]] , 2 [complexRoots= ? - 6? + 6, coordinates= [a - 1,b - 1,c - 1,d - %A + 5,e + %A - 1,f - 1]] ] Type: List Record(complexRoots: SparseUnivariatePolynomial Integer, coordinates: List Polynomial Integer) Since the univariateSolve operation may split a regular set, it returns a list. This explains the use of concat. Look at the last item of the result. It consists of two parts. For any complex root ? of the univariate polynomial in the first part, we get a tuple of univariate polynomials (in a, ...,f respectively) by replacing %A by ? in the second part. Each of these tuples t describes a point of the variety associated with lp by equaling to zero the polynomials in t. Note that the way of reading these univariate representations is explained also in the example illustrating the ZeroDimensionalSolvePackage constructor. Now, we compute the points of the variety with real coordinates. :: concat [realSolve(ts)$zdpack for ts in lts] [[%B1,%B1,%B1,%B5,- %B5 - 4%B1,%B1], [%B1,%B1,%B1,%B6,- %B6 - 4%B1,%B1], [%B2,%B2,%B2,%B3,- %B3 - 4%B2,%B2], [%B2,%B2,%B2,%B4,- %B4 - 4%B2,%B2], [%B7,%B7,%B7,%B7,%B11,- %B11 - 4%B7], [%B7,%B7,%B7,%B7,%B12,- %B12 - 4%B7], [%B8,%B8,%B8,%B8,%B9,- %B9 - 4%B8], [%B8,%B8,%B8,%B8,%B10,- %B10 - 4%B8], [%B13,%B13,%B17,- %B17 - 4%B13,%B13,%B13], [%B13,%B13,%B18,- %B18 - 4%B13,%B13,%B13], [%B14,%B14,%B15,- %B15 - 4%B14,%B14,%B14], [%B14,%B14,%B16,- %B16 - 4%B14,%B14,%B14], [%B19, %B29, 7865521 31 6696179241 25 25769893181 19 ---------- %B19 - ---------- %B19 - ----------- %B19 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B19 - ------------- %B19 - ----------- %B19 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B19 + ------------- %B19 + --------------- %B19 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B19 + --------------- %B19 - ------------ %B19 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B19 - ------------- %B19 - --------------- %B19 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B19 - --------------- %B19 - ------------- %B19 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B29 - ------------- %B19 + ------------ %B19 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B19 + ---------------- %B19 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B19 + -------------- %B19 1387545279120 1387545279120 ] , [%B19, %B30, 7865521 31 6696179241 25 25769893181 19 ---------- %B19 - ---------- %B19 - ----------- %B19 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B19 - ------------- %B19 - ----------- %B19 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B19 + ------------- %B19 + --------------- %B19 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B19 + --------------- %B19 - ------------ %B19 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B19 - ------------- %B19 - --------------- %B19 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B19 - --------------- %B19 - ------------- %B19 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B30 - ------------- %B19 + ------------ %B19 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B19 + ---------------- %B19 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B19 + -------------- %B19 1387545279120 1387545279120 ] , [%B20, %B27, 7865521 31 6696179241 25 25769893181 19 ---------- %B20 - ---------- %B20 - ----------- %B20 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B20 - ------------- %B20 - ----------- %B20 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B20 + ------------- %B20 + --------------- %B20 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B20 + --------------- %B20 - ------------ %B20 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B20 - ------------- %B20 - --------------- %B20 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B20 - --------------- %B20 - ------------- %B20 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B27 - ------------- %B20 + ------------ %B20 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B20 + ---------------- %B20 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B20 + -------------- %B20 1387545279120 1387545279120 ] , [%B20, %B28, 7865521 31 6696179241 25 25769893181 19 ---------- %B20 - ---------- %B20 - ----------- %B20 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B20 - ------------- %B20 - ----------- %B20 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B20 + ------------- %B20 + --------------- %B20 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B20 + --------------- %B20 - ------------ %B20 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B20 - ------------- %B20 - --------------- %B20 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B20 - --------------- %B20 - ------------- %B20 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B28 - ------------- %B20 + ------------ %B20 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B20 + ---------------- %B20 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B20 + -------------- %B20 1387545279120 1387545279120 ] , [%B21, %B25, 7865521 31 6696179241 25 25769893181 19 ---------- %B21 - ---------- %B21 - ----------- %B21 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B21 - ------------- %B21 - ----------- %B21 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B21 + ------------- %B21 + --------------- %B21 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B21 + --------------- %B21 - ------------ %B21 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B21 - ------------- %B21 - --------------- %B21 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B21 - --------------- %B21 - ------------- %B21 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B25 - ------------- %B21 + ------------ %B21 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B21 + ---------------- %B21 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B21 + -------------- %B21 1387545279120 1387545279120 ] , [%B21, %B26, 7865521 31 6696179241 25 25769893181 19 ---------- %B21 - ---------- %B21 - ----------- %B21 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B21 - ------------- %B21 - ----------- %B21 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B21 + ------------- %B21 + --------------- %B21 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B21 + --------------- %B21 - ------------ %B21 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B21 - ------------- %B21 - --------------- %B21 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B21 - --------------- %B21 - ------------- %B21 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B26 - ------------- %B21 + ------------ %B21 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B21 + ---------------- %B21 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B21 + -------------- %B21 1387545279120 1387545279120 ] , [%B22, %B23, 7865521 31 6696179241 25 25769893181 19 ---------- %B22 - ---------- %B22 - ----------- %B22 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B22 - ------------- %B22 - ----------- %B22 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B22 + ------------- %B22 + --------------- %B22 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B22 + --------------- %B22 - ------------ %B22 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B22 - ------------- %B22 - --------------- %B22 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B22 - --------------- %B22 - ------------- %B22 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B23 - ------------- %B22 + ------------ %B22 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B22 + ---------------- %B22 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B22 + -------------- %B22 1387545279120 1387545279120 ] , [%B22, %B24, 7865521 31 6696179241 25 25769893181 19 ---------- %B22 - ---------- %B22 - ----------- %B22 6006689520 2002229840 49235160 + 1975912990729 13 1048460696489 7 21252634831 - ------------- %B22 - ------------- %B22 - ----------- %B22 3003344760 2002229840 6006689520 , 778171189 31 1987468196267 25 155496778477189 19 - ------------- %B22 + ------------- %B22 + --------------- %B22 1387545279120 1387545279120 693772639560 + 191631411158401 13 300335488637543 7 755656433863 --------------- %B22 + --------------- %B22 - ------------ %B22 693772639560 1387545279120 198220754160 , 1094352947 31 2794979430821 25 218708802908737 19 ------------ %B22 - ------------- %B22 - --------------- %B22 462515093040 462515093040 231257546520 + 91476663003591 13 145152550961823 7 1564893370717 - -------------- %B22 - --------------- %B22 - ------------- %B22 77085848840 154171697680 462515093040 , 4321823003 31 180949546069 25 - %B24 - ------------- %B22 + ------------ %B22 1387545279120 22746643920 + 863753195062493 19 1088094456732317 13 --------------- %B22 + ---------------- %B22 693772639560 693772639560 + 1732620732685741 7 13506088516033 ---------------- %B22 + -------------- %B22 1387545279120 1387545279120 ] , [%B31,%B35,- %B35 - 4%B31,%B31,%B31,%B31], [%B31,%B36,- %B36 - 4%B31,%B31,%B31,%B31], [%B32,%B33,- %B33 - 4%B32,%B32,%B32,%B32], [%B32,%B34,- %B34 - 4%B32,%B32,%B32,%B32]] Type: List List RealClosure Fraction Integer We obtain 24 points given by lists of elements in the RealClosure of Fraction of R. In each list, the first value corresponds to the indeterminate f, the second to e and so on. .. [Lazard] D. Lazard, *Solving Zero-dimensional Algebraic Systems*, J. of Symbol. Comput., 1992 .. [Faugere] Faugere et al., *Efficient Computation of Zero-Dimensional* *Groebner Bases by Change of Ordering*, J. of Symbol. Comput., 1993 See Also: * )help RegularChain * )help RegularTriangularSet * )help SquareFreeRegularTriangularSet * )help ZeroDimensionalSolvePackage * )help NewSparseMultivariatePolynomial * )help LinGroebnerPackage * )help NormalizedTriangularSetCategory * )help RealClosure * )help Fraction * )show LexTriangularPackage