9.67 RegularTriangularSet¶

The RegularTriangularSet domain constructor implements regular triangular sets. These particular triangular sets were introduced by M. Kalkbrener (1991) in his PhD Thesis under the name regular chains. Regular chains and their related concepts are presented in the paper On the Theories of Triangular sets By P. Aubry, D. Lazard and M. Moreno Maza (to appear in the Journal of Symbolic Computation). The RegularTriangularSet constructor also provides a new method (by the third author) for solving polynomial system by means of regular chains. This method has two ways of solving. One has the same specifications as Kalkbrener’s algorithm (1991) and the other is closer to Lazard’s method (Discr. App. Math, 1991). Moreover, this new method removes redundant component from the decompositions when this is not too expensive. This is always the case with square-free regular chains. So if you want to obtain decompositions without redundant components just use the SquareFreeRegularTriangularSet domain constructor or the LazardSetSolvingPackage package constructor. See also the LexTriangularPackage and ZeroDimensionalSolvePackage for the case of algebraic systems with a finite number of (complex) solutions.

One of the main features of regular triangular sets is that they naturally define towers of simple extensions of a field. This allows to perform with multivariate polynomials the same kind of operations as one can do in an EuclideanDomain.

The RegularTriangularSet constructor takes four arguments. The first one, R, is the coefficient ring of the polynomials; it must belong to the category GcdDomain. The second one, E, is the exponent monoid of the polynomials; it must belong to the category OrderedAbelianMonoidSup. the third one, V, is the ordered set of variables; it must belong to the category OrderedSet. The last one is the polynomial ring; it must belong to the category RecursivePolynomialCategory(R,E,V). The abbreviation for RegularTriangularSet is REGSET. See also the constructor RegularChain which only takes two arguments, the coefficient ring and the ordered set of variables; in that case, polynomials are necessarily built with the NewSparseMultivariatePolynomial domain constructor.

We shall explain now how to use the constructor REGSET and how to read the decomposition of a polynomial system by means of regular sets.

Let us give some examples. We start with an easy one (Donati-Traverso) in order to understand the two ways of solving polynomial systems provided by the REGSET constructor.

Define the coefficient ring.

R := Integer

\[\]

Integer

_{Type: Domain}

Define the list of variables,

ls : List Symbol := [x,y,z,t]

\[\]

[x,y,z,t]

_{Type: List Symbol}

and make it an ordered set;

V := OVAR(ls)

\[\]

OrderedVariableList[x,y,z,t]

_{Type: Domain}

then define the exponent monoid.

E := IndexedExponents V

\[\]

IndexedExponentsOrderedVariableList[x,y,z,t]

_{Type: Domain}

Define the polynomial ring.

P := NSMP(R, V)

\[\]

NewSparseMultivariatePolynomial(Integer,OrderedVariableList[x,y,z,t])

_{Type: Domain}

Let the variables be polynomial.

x: P := 'x

\[\]

x

_{Type: NewSparseMultivariatePolynomial( Integer, OrderedVariableList} [x,y,z,t])

y: P := 'y

\[\]

y

_{Type: NewSparseMultivariatePolynomial( Integer, OrderedVariableList} [x,y,z,t])

z: P := 'z

\[\]

z

_{Type: NewSparseMultivariatePolynomial( Integer, OrderedVariableList} [x,y,z,t])

t: P := 't

\[\]

t

_{Type: NewSparseMultivariatePolynomial( Integer, OrderedVariableList} [x,y,z,t])

Now call the RegularTriangularSet domain constructor.

T := REGSET(R,E,V,P)

\[\]

RegularTriangularSet(Integer, IndexedExponentsOrderedVariableList[x,y,z,t], OrderedVariableList[x,y,z,t], NewSparseMultivariatePolynomial(Integer, OrderedVariableList[x,y,z,t]))

_{Type: Domain}

Define a polynomial system.

p1 := x ^ 31 - x ^ 6 - x - y

\[\]

x31-x6-x-y

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

p2 := x ^ 8 - z

\[\]

x8-z

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

p3 := x ^ 10 - t

\[\]

x10-t

_{Type: NewSparseMultivariatePolynomial( Integer, OrderedVariableList} [x,y,z,t])

lp := [p1, p2, p3]

\[\]

[x31-x6-x-y,x8-z,x10-t]

_{Type: List NewSparseMultivariatePolynomial( Integer, OrderedVariableList} [x,y,z,t])

First of all, let us solve this system in the sense of Kalkbrener.

zeroSetSplit(lp)$T

\[\]

[{z5-t4,tzy2+2z3y-t8+2t5+t3-t2,(t4-t)x-ty-z2}]

_{Type: List RegularTriangularSet( Integer, IndexedExponents} OrderedVariableList [x,y,z,t], OrderedVariableList [x,y,z,t], NewSparseMultivariatePolynomial( Integer, OrderedVariableList [x,y,z,t]))

And now in the sense of Lazard (or Wu and other authors).

lts := zeroSetSplit(lp,false)$T

\[\]

[{z5-t4,tzy2+2z3y-t8+2t5+t3-t2,(t4-t)x-ty-z2},{t3-1,z5-t,tzy2+2z3y+1,zx2-t},{t,z,y,x}]

_{Type: List RegularTriangularSet( Integer, IndexedExponents} OrderedVariableList [x,y,z,t], OrderedVariableList [x,y,z,t], NewSparseMultivariatePolynomial( Integer, OrderedVariableList [x,y,z,t]))

We can see that the first decomposition is a subset of the second. So how can both be correct ?

Recall first that polynomials from a domain of the category RecursivePolynomialCategory are regarded as univariate polynomials in their main variable. For instance the second polynomial in the first set of each decomposition has main variable y and its initial (i.e. its leading coefficient w.r.t. its main variable) is t z.

Now let us explain how to read the second decomposition. Note that the non-constant initials of the first set are t4-t and tz. Then the solutions described by this first set are the common zeros of its polynomials that do not cancel the polynomials t4-t and tyz. Now the solutions of the input system lp satisfying these equations are described by the second and the third sets of the decomposition. Thus, in some sense, they can be considered as degenerated solutions. The solutions given by the first set are called the generic points of the system; they give the general form of the solutions. The first decomposition only provides these generic points. This latter decomposition is useful when they are many degenerated solutions (which is sometimes hard to compute) and when one is only interested in general informations, like the dimension of the input system.

We can get the dimensions of each component of a decomposition as follows.

[coHeight(ts) for ts in lts]

\[\]

[1,0,0]

_{Type: List NonNegativeInteger}

Thus the first set has dimension one. Indeed t can take any value, except 0 or any third root of 1, whereas z is completely determined from t, y is given by z and t, and finally x is given by the other three variables. In the second and the third sets of the second decomposition the four variables are completely determined and thus these sets have dimension zero.

We give now the precise specifications of each decomposition. This assume some mathematical knowledge. However, for the non-expert user, the above explanations will be sufficient to understand the other features of the RSEGSET constructor.

The input system lp is decomposed in the sense of Kalkbrener as finitely many regular sets T1,...,Ts such that the radical ideal generated by lp is the intersection of the radicals of the saturated ideals of T1,...,Ts. In other words, the affine variety associated with lp is the union of the closures (w.r.t. Zarisky topology) of the regular-zeros sets of T1,...,Ts.

The prime ideals associated with the radical of the saturated

ideal of a regular triangular set have all the same dimension; moreover these prime ideals can be given by characteristic sets with the same main variables. Thus a decomposition in the sense of Kalkbrener is unmixed dimensional. Then it can be viewed as a lazy decomposition into prime ideals (some of these prime ideals being merged into unmixed dimensional ideals).

Now we explain the other way of solving by means of regular triangular sets. The input system lp is decomposed in the sense of Lazard as finitely many regular triangular sets T1,...,Ts such that the affine variety associated with lp is the union of the regular-zeros sets of T1,...,Ts. Thus a decomposition in the sense of Lazard is also a decomposition in the sense of Kalkbrener; the converse is false as we have seen before.

When the input system has a finite number of solutions, both ways of solving provide similar decompositions as we shall see with this second example (Caprasse).

Define a polynomial system.

f1 := y^2*z+2*x*y*t-2*x-z

\[\]

(2ty-2)x+zy2-z

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

f2 := -x^3*z+ 4*x*y^2*z+ 4*x^2*y*t+ 2*y^3*t+ 4*x^2- 10*y^2+

4*x*z- 10*y*t+ 2

\[\]

-zx3+(4ty+4)x2+(4zy2+4z)x+2ty3-10y2-10ty+2

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

f3 := 2*y*z*t+x*t^2-x-2*z

\[\]

(t2-1)x+2tzy-2z

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

f4 := -x*z^3+ 4*y*z^2*t+ 4*x*z*t^2+ 2*y*t^3+ 4*x*z+

4*z^2-10*y*t- 10*t^2+2

\[\]

(-z3+(4t2+4)z)x+(4tz2+2t3-10t)y+4z2-10t2+2

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

lf := [f1, f2, f3, f4]

\[\]

[(2ty-2)x+zy2-z,-zx3+(4ty+4)x2+(4zy2+4z)x+2ty3-10y2-10ty+2,(t2-1)x+2tzy-2z,(-z3+(4t2+4)z)x+(4tz2+2t3-10t)y+4z2-10t2+2]

_{Type: List NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

First of all, let us solve this system in the sense of Kalkbrener.

zeroSetSplit(lf)$T

\[\]

[{t2-1,z8-16z6+256z2-256,ty-1,(z3-8z)x-8z2+16},{3t2+1,z2-7t2-1,y+t,x+z},{t8-10t6+10t2-1,z,(t3-5t)y-5t2+1,x},{t2+3,z2-4,y+t,x-z}]

_{Type: List RegularTriangularSet(Integer, IndexedExponents} OrderedVariableList [x,y,z,t], OrderedVariableList [x,y,z,t], NewSparseMultivariatePolynomial(Integer, OrderedVariableList [x,y,z,t]))

And now in the sense of Lazard (or Wu and other authors).

lts2 := zeroSetSplit(lf,false)$T

\[\]

[{t8-10t6+10t2-1,z,(t3-5t)y-5t2+1,x},{t2-1,z8-16z6+256z2-256,ty-1,(z3-8z)x-8z2+16},{3t2+1,z2-7t2-1,y+t,x+z},{t2+3,z2-4,y+t,x-z}]

_{Type: List RegularTriangularSet(Integer, IndexedExponents} OrderedVariableList [x,y,z,t], OrderedVariableList [x,y,z,t], NewSparseMultivariatePolynomial(Integer, OrderedVariableList [x,y,z,t]))

Up to the ordering of the components, both decompositions are identical.

Let us check that each component has a finite number of solutions.

[coHeight(ts) for ts in lts2]

\[\]

[0,0,0,0]

_{Type: List NonNegativeInteger}

Let us count the degrees of each component,

degrees := [degree(ts) for ts in lts2]

\[\]

[8,16,4,4]

_{Type: List NonNegativeInteger}

and compute their sum.

reduce(+,degrees)

\[\]

32

_{Type: PositiveInteger}

We study now the options of the zeroSetSplit operation. As we have seen yet, there is an optional second argument which is a boolean value. If this value is true (this is the default) then the decomposition is computed in the sense of Kalkbrener, otherwise it is computed in the sense of Lazard.

There is a second boolean optional argument that can be used (in that case the first optional argument must be present). This second option allows you to get some information during the computations.

Therefore, we need to understand a little what is going on during the computations. An important feature of the algorithm is that the intermediate computations are managed in some sense like the processes of a Unix system. Indeed, each intermediate computation may generate other intermediate computations and the management of all these computations is a crucial task for the efficiency. Thus any intermediate computation may be suspended, killed or resumed, depending on algebraic considerations that determine priorities for these processes. The goal is of course to go as fast as possible towards the final decomposition which means to avoid as much as possible unnecessary computations.

To follow the computations, one needs to set to true the second argument. Then a lot of numbers and letters are displayed. Between a [ and a ] one has the state of the processes at a given time. Just after [ one can see the number of processes. Then each process is represented by two numbers between < and >. A process consists of a list of polynomial ps and a triangular set ts; its goal is to compute the common zeros of ps that belong to the regular-zeros set of ts. After the processes, the number between pipes gives the total number of polynomials in all the sets ps. Finally, the number between braces gives the number of components of a decomposition that are already computed. This number may decrease.

Let us take a third example (Czapor-Geddes-Wang) to see how this information is displayed.

Define a polynomial system.

u : R := 2

\[\]

2

_{Type: Integer}

q1 := 2*(u-1)^2+ 2*(x-z*x+z^2)+ y^2*(x-1)^2- 2*u*x+

2*y*t*(1-x)*(x-z)+ 2*u*z*t*(t-y)+ u^2*t^2*(1-2*z)+ 2*u*t^2*(z-x)+ 2*u*t*y*(z-1)+ 2*u*z*x*(y+1)+ (u^2-2*u)*z^2*t^2+ 2*u^2*z^2+ 4*u*(1-u)*z+ t^2*(z-x)^2

\[\]

(y2-2ty+t2)x2+(-2y2+((2t+4)z+2t)y+(-2t2+2)z-4t2-2)x+y2+(-2tz-4t)y+(t2+10)z2-8z+4t2+2

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

q2 := t*(2*z+1)*(x-z)+ y*(z+2)*(1-x)+ u*(u-2)*t+

u*(1-2*u)*z*t+ u*y*(x+u-z*x-1)+ u*(u+1)*z^2*t

\[\]

(-3zy+2tz+t)x+(z+4)y+4tz2-7tz

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

q3 := -u^2*(z-1)^2+ 2*z*(z-x)-2*(x-1)

\[\]

(-2z-2)x-2z2+8z-2

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

q4 := u^2+4*(z-x^2)+3*y^2*(x-1)^2- 3*t^2*(z-x)^2

+3*u^2*t^2*(z-1)^2+u^2*z*(z-2)+6*u*t*y*(z+x+z*x-1)

\[\]

(3y2-3t2-4)x2+(-6y2+(12tz+12t)y+6t2z)x+3y2+(12tz-12t)y+(9t2+4)z2+(-24t2-4)z+12t2+4

_{Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

lq := [q1, q2, q3, q4]

\[\]

[(y2-2ty+t2)x2+(-2y2+((2t+4)z+2t)y+(-2t2+2)z-4t2-2)x+y2+(-2tz-4t)y+(t2+10)z2-8z+4t2+2,(-3zy+2tz+t)x+(z+4)y+4tz2-7tz,(-2z-2)x-2z2+8z-2,(3y2-3t2-4)x2+(-6y2+(12tz+12t)y+6t2z)x+3y2+(12tz-12t)y+(9t2+4)z2+(-24t2-4)z+12t2+4]

_{Type: List NewSparseMultivariatePolynomial(Integer,OrderedVariableList} [x,y,z,t])

Let us try the information option. N.B. The timing should be between 1 and 10 minutes, depending on your machine.

zeroSetSplit(lq,true,true)$T

[1 <4,0> -> |4|; {0}]W[2 <5,0>,<3,1> -> |8|; {0}][2 <4,1>,<3,1> -> |7|;

{0}][1 <3,1> -> |3|; {0}]G[2 <4,1>,<4,1> -> |8|; {0}]W[3 <5,1>,<4,1>,: <3,2> -> |12|; {0}]GI[3 <4,2>,<4,1>,<3,2> -> |11|; {0}]GWw[3 <4,1>, <3,2>,<5,2> -> |12|; {0}][3 <3,2>,<3,2>,<5,2> -> |11|; {0}]GIwWWWw
[4 <3,2>,<4,2>,<5,2>,<2,3> -> |14|; {0}][4 <2,2>,<4,2>,<5,2>,<2,3> ->: |13|; {0}]Gwww[5 <3,2>,<3,2>,<4,2>,<5,2>,<2,3> -> |17|; {0}]Gwwwwww
[8 <3,2>,<4,2>,<4,2>,<4,2>,<4,2>,<4,2>,<5,2>,<2,3> -> |30|; {0}]Gwwwwww: [8 <4,2>,<4,2>,<4,2>,<4,2>,<4,2>,<4,2>,<5,2>,<2,3> -> |31|; {0}][8

<3,3>,<4,2>,<4,2>,<4,2>,<4,2>,<4,2>,<5,2>,<2,3> -> |30|; {0}][8 <2,3>,

<4,2>,<4,2>,<4,2>,<4,2>,<4,2>,<5,2>,<2,3> -> |29|; {0}][8 <1,3>,<4,2>,

<4,2>,<4,2>,<4,2>,<4,2>,<5,2>,<2,3> -> |28|; {0}][7 <4,2>,<4,2>,<4,2>,

<4,2>,<4,2>,<5,2>,<2,3> -> |27|; {0}][6 <4,2>,<4,2>,<4,2>,<4,2>,<5,2>,: <2,3> -> |23|; {0}][5 <4,2>,<4,2>,<4,2>,<5,2>,<2,3> -> |19|; {0}] GIGIWwww[6 <5,2>,<4,2>,<4,2>,<5,2>,<3,3>,<2,3> -> |23|; {0}][6 <4,3>, <4,2>,<4,2>,<5,2>,<3,3>,<2,3> -> |22|; {0}]GIGI[6 <3,4>,<4,2>,<4,2>,

<5,2>,<3,3>,<2,3> -> |21|; {0}][6 <2,4>,<4,2>,<4,2>,<5,2>,<3,3>,<2,3>

-> |20|; {0}]GGG[5 <4,2>,<4,2>,<5,2>,<3,3>,<2,3> -> |18|; {0}]GIGIWwwwW: [6 <5,2>,<4,2>,<5,2>,<3,3>,<3,3>,<2,3> -> |22|; {0}][6 <4,3>,<4,2>, <5,2>,<3,3>,<3,3>,<2,3> -> |21|; {0}]GIwwWwWWWWWWWwWWWWwwwww[8 <4,2>,

<5,2>,<3,3>,<3,3>,<4,3>,<2,3>,<3,4>,<3,4> -> |27|; {0}][8 <3,3>,<5,2>,

<3,3>,<3,3>,<4,3>,<2,3>,<3,4>,<3,4> -> |26|; {0}][8 <2,3>,<5,2>,<3,3>,: <3,3>,<4,3>,<2,3>,<3,4>,<3,4> -> |25|; {0}]Gwwwwwwwwwwwwwwwwwwww[9 <5,2>,<3,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,4>,<3,4> -> |29|; {0}] GI[9 <4,3>,<3,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,4>,<3,4> -> |28|;

{0}][9 <3,3>,<3,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,4>,<3,4> -> |27|;

{0}][9 <2,3>,<3,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,4>,<3,4> -> |26|;: {0}]GGwwwwwwwwwwwwWWwwwwwwww[11 <3,3>,<3,3>,<3,3>,<3,3>,<4,3>,<2,3>,

<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |33|; {0}][11 <2,3>,<3,3>,<3,3>,<3,3>,

<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |32|; {0}][11 <1,3>,<3,3>,

<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |31|; {0}]
GGGwwwwwwwwwwwww[12 <2,3>,<2,3>,<3,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,
<3,3>,<3,3>,<3,4>,<3,4> -> |34|; {0}]GGwwwwwwwwwwwww[13 <3,3>,<2,3>,
<3,3>,<3,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> ->

|38|; {0}]Gwwwwwwwwwwwww[13 <2,3>,<3,3>,<4,3>,<3,3>,<4,3>,<3,3>,<3,3>,: <2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |39|; {0}]GGGwwwwwwwwwwwww[15

<3,3>,<4,3>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,

<3,3>,<3,4>,<3,4> -> |46|; {0}][14 <4,3>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,

<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |43|; {0}]GIGGGGIGGI: [14 <3,4>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,

<3,3>,<3,4>,<3,4> -> |42|; {0}]GGG[14 <2,4>,<3,3>,<3,3>,<3,3>,<3,3>,
<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |41|; {0}]
[14 <1,4>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,
<3,3>,<3,4>,<3,4> -> |40|; {0}]GGG[13 <3,3>,<3,3>,<3,3>,<3,3>,<3,3>,
<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |39|; {0}]
Gwwwwwwwwwwwww[15 <3,3>,<3,3>,<4,3>,<4,3>,<4,3>,<3,3>,<3,3>,<4,3>,
<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |48|; {0}]Gwwwwwwwwwwwww
[15 <4,3>,<4,3>,<3,3>,<4,3>,<4,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,3>,
<3,3>,<3,3>,<3,4>,<3,4> -> |49|; {0}]GIGI[15 <3,4>,<4,3>,<3,3>,<4,3>,
<4,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> ->

|48|; {0}]G[14 <4,3>,<3,3>,<4,3>,<4,3>,<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,
<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |45|; {0}][13 <3,3>,<4,3>,<4,3>,
<3,3>,<4,3>,<3,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |41|;
{0}]Gwwwwwwwwwwwww[13 <4,3>,<4,3>,<4,3>,<3,3>,<3,3>,<4,3>,<3,3>,<2,3>,
<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |42|; {0}]GIGGGGIGGI[13 <3,4>,<4,3>,
<4,3>,<3,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> ->

|41|; {0}]GGGGGGGG[13 <2,4>,<4,3>,<4,3>,<3,3>,<3,3>,<4,3>,<3,3>,<2,3>,

<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |40|; {0}][13 <1,4>,<4,3>,<4,3>,<3,3>,: <3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |39|; {0}] [13 <0,4>,<4,3>,<4,3>,<3,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,

<3,4>,<3,4> -> |38|; {0}][12 <4,3>,<4,3>,<3,3>,<3,3>,<4,3>,<3,3>,
<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |38|; {1}][11 <4,3>,<3,3>,
<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |34|; {1}]
[10 <3,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> ->
|30|; {1}][10 <2,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,
<3,4> -> |29|; {1}]GGGwwwwwwwwwwwww[11 <3,3>,<3,3>,<4,3>,<3,3>,
<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |33|; {1}]
GGGwwwwwwwwwwwww[12 <4,3>,<3,3>,<4,3>,<3,3>,<3,3>,<4,3>,
<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |38|; {1}]Gwwwwwwwwwwwww
[12 <3,3>,<4,3>,<5,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,

<3,4>,<3,4> -> |39|; {1}]GGwwwwwwwwwwwww[13 <5,3>,<4,3>,<4,3>,
<4,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> ->
|44|; {1}]GIGGGGIGGIW[13 <4,4>,<4,3>,<4,3>,<4,3>,<3,3>,<3,3>,
<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |43|; {1}]GGW[13
<3,4>,<4,3>,<4,3>,<4,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,
<3,4>,<3,4> -> |42|; {1}]GGG[12 <4,3>,<4,3>,<4,3>,<3,3>,<3,3>,<4,3>,
<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |39|; {1}]Gwwwwwwwwwwwww[12
<4,3>,<4,3>,<5,3>,<3,3>,<4,3>,<3,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,
<3,4> -> |40|; {1}]Gwwwwwwwwwwwww[13 <5,3>,<5,3>,<4,3>,<5,3>,<3,3>,
<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |46|; {1}]GIGIW

[13 <4,4>,<5,3>,<4,3>,<5,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,
<3,3>,<3,4>,<3,4> -> |45|; {1}][13 <3,4>,<5,3>,<4,3>,<5,3>,<3,3>,
<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |44|; {1}][13
<2,4>,<5,3>,<4,3>,<5,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,
<3,4>,<3,4> -> |43|; {1}]GG[12 <5,3>,<4,3>,<5,3>,<3,3>,<3,3>,<4,3>,
<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |41|; {1}]GIGGGGIGGIW[12
<4,4>,<4,3>,<5,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,
<3,4> -> |40|; {1}]GGGGGGW[12 <3,4>,<4,3>,<5,3>,<3,3>,<3,3>,<4,3>,
<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |39|; {1}][12 <2,4>,<4,3>,
<5,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |38|;

{1}][12 <1,4>,<4,3>,<5,3>,<3,3>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,
<3,4>,<3,4> -> |37|; {1}]GGG[11 <4,3>,<5,3>,<3,3>,<3,3>,<4,3>,<2,3>,
<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |36|; {1}][10 <5,3>,<3,3>,<3,3>,
<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |32|; {1}][9 <3,3>,
<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |27|; {1}]W[9
<2,4>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |26|; {1}]
[9 <1,4>,<3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |25|;
{1}][8 <3,3>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |24|; {1}]
W[8 <2,4>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |23|; {1}][8

<1,4>,<4,3>,<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |22|; {1}][7 <4,3>,

<2,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |21|; {1}]w[7 <3,4>,<2,3>,
<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |20|; {1}][7 <2,4>,<2,3>,<3,3>,
<3,3>,<3,3>,<3,4>,<3,4> -> |19|; {1}][7 <1,4>,<2,3>,<3,3>,<3,3>,
<3,3>,<3,4>,<3,4> -> |18|; {1}][6 <2,3>,<3,3>,<3,3>,<3,3>,<3,4>,
<3,4> -> |17|; {1}]GGwwwwww[7 <3,3>,<3,3>,<3,3>,<3,3>,<3,3>,<3,4>,
<3,4> -> |21|; {1}]GIW[7 <2,4>,<3,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4>
-> |20|; {1}]GG[6 <3,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |18|; {1}]
Gwwwwww[7 <4,3>,<4,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |23|; {1}]
GIW[7 <3,4>,<4,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |22|; {1}][6
<4,3>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |19|; {1}]GIW[6 <3,4>,<3,3>,

<3,3>,<3,3>,<3,4>,<3,4> -> |18|; {1}]GGW[6 <2,4>,<3,3>,<3,3>,<3,3>,
<3,4>,<3,4> -> |17|; {1}][6 <1,4>,<3,3>,<3,3>,<3,3>,<3,4>,<3,4> ->
|16|; {1}]GGG[5 <3,3>,<3,3>,<3,3>,<3,4>,<3,4> -> |15|; {1}]GIW[5
<2,4>,<3,3>,<3,3>,<3,4>,<3,4> -> |14|; {1}]GG[4 <3,3>,<3,3>,<3,4>,

<3,4> -> |12|; {1}][3 <3,3>,<3,4>,<3,4> -> |9|; {1}]W[3 <2,4>,<3,4>,: <3,4> -> |8|; {1}][3 <1,4>,<3,4>,<3,4> -> |7|; {1}]G[2 <3,4>,<3,4>
-> |6|; {1}]G[1 <3,4> -> |3|; {1}][1 <2,4> -> |2|; {1}][1 <1,4> ->: |1|; {1}]

^* QCMPACK Statistics ^*
   Table     size:  36
   Entries reused:  255
^* REGSETGCD: Gcd Statistics ^*
   Table     size:  125
   Entries reused:  0
^* REGSETGCD: Inv Set Statistics ^*
   Table     size:  30
   Entries reused:  0

\[\]

(26604210869491302385515265737052082361668474181372891857784t23+443104378424686086067294899528296664238693556855017735265295t22+279078393286701234679141342358988327155321305829547090310242t21+3390276361413232465107617176615543054620626391823613392185226t20+941478179503540575554198645220352803719793196473813837434129t19+11547855194679475242211696749673949352585747674184320988144390t18+1343609566765597789881701656699413216467215660333356417241432t17+23233813868147873503933551617175640859899102987800663566699334t16+869574020537672336950845440508790740850931336484983573386433t15+31561554305876934875419461486969926554241750065103460820476969t14+ 1271400990287717487442065952547731879554823889855386072264931t13+31945089913863736044802526964079540198337049550503295825160523t12+3738735704288144509871371560232845884439102270778010470931960t11+25293997512391412026144601435771131587561905532992045692885927t10+5210239009846067123469262799870052773410471135950175008046524t9+15083887986930297166259870568608270427403187606238713491129188t8+3522087234692930126383686270775779553481769125670839075109000t7+6079945200395681013086533792568886491101244247440034969288588t6+1090634852433900888199913756247986023196987723469934933603680t5+1405819430871907102294432537538335402102838994019667487458352t4+ 88071527950320450072536671265507748878347828884933605202432t3+135882489433640933229781177155977768016065765482378657129440t2-13957283442882262230559894607400314082516690749975646520320t+334637692973189299277258325709308472592117112855749713920)z+8567175484043952879756725964506833932149637101090521164936t23+149792392864201791845708374032728942498797519251667250945721t22+77258371783645822157410861582159764138123003074190374021550t21+1108862254126854214498918940708612211184560556764334742191654t20+213250494460678865219774480106826053783815789621501732672327t19+ 3668929075160666195729177894178343514501987898410131431699882t18+171388906471001872879490124368748236314765459039567820048872t17+7192430746914602166660233477331022483144921771645523139658986t16-128798674689690072812879965633090291959663143108437362453385t15+9553010858341425909306423132921134040856028790803526430270671t14-13296096245675492874538687646300437824658458709144441096603t13+9475806805814145326383085518325333106881690568644274964864413t12+803234687925133458861659855664084927606298794799856265539336t11+7338202759292865165994622349207516400662174302614595173333825t10+1308004628480367351164369613111971668880538855640917200187108t9+ 4268059455741255498880229598973705747098216067697754352634748t8+892893526858514095791318775904093300103045601514470613580600t7+1679152575460683956631925852181341501981598137465328797013652t6+269757415767922980378967154143357835544113158280591408043936t5+380951527864657529033580829801282724081345372680202920198224t4+19785545294228495032998826937601341132725035339452913286656t3+36477412057384782942366635303396637763303928174935079178528t2-3722212879279038648713080422224976273210890229485838670848t+89079724853114348361230634484013862024728599906874105856, (3z3-11z2+8z+4)y+2tz3+4tz2-5tz-t,:(z+1)x+z2-4z+1}]

_{Type: List RegularTriangularSet( Integer, IndexedExponents} OrderedVariableList [x,y,z,t], OrderedVariableList [x,y,z,t], NewSparseMultivariatePolynomial(Integer, OrderedVariableList [x,y,z,t]))

Between a sequence of processes, thus between a ] and a [ you can see capital letters W, G, I and lower case letters i, w. Each time a capital letter appears a non-trivial computation has be performed and its result is put in a hash-table. Each time a lower case letter appears a needed result has been found in an hash-table. The use of these hash-tables generally speed up the computations. However, on very large systems, it may happen that these hash-tables become too big to be handle by your AXIOM configuration. Then in these exceptional cases, you may prefer getting a result (even if it takes a long time) than getting nothing. Hence you need to know how to prevent the RSEGSET constructor from using these hash-tables. In that case you will be using the zeroSetSplit with five arguments. The first one is the input system lp as above. The second one is a boolean value hash? which is true iff you want to use hash-tables. The third one is boolean value clos? which is true iff you want to solve your system in the sense of Kalkbrener, the other way remaining that of Lazard. The fourth argument is boolean value info? which is true iff you want to display information during the computations. The last one is boolean value prep? which is true iff you want to use some heuristics that are performed on the input system before starting the real algorithm. The value of this flag is true when you are using zeroSetSplit with less than five arguments. Note that there is no available signature for zeroSetSplit with four arguments.

We finish this section by some remarks about both ways of solving, in the sense of Kalkbrener or in the sense of Lazard. For problems with a finite number of solutions, there are theoretically equivalent and the resulting decompositions are identical, up to the ordering of the components. However, when solving in the sense of Lazard, the algorithm behaves differently. In that case, it becomes more incremental than in the sense of Kalkbrener. That means the polynomials of the input system are considered one after another whereas in the sense of Kalkbrener the input system is treated more globally.

This makes an important difference in positive dimension. Indeed when solving in the sense of Kalkbrener, the Primeidealkettensatz of Krull is used. That means any regular triangular containing more polynomials than the input system can be deleted. This is not possible when solving in the sense of Lazard. This explains why Kalkbrener’s decompositions usually contain less components than those of Lazard. However, it may happen with some examples that the incremental process (that cannot be used when solving in the sense of Kalkbrener) provide a more efficient way of solving than the global one even if the Primeidealkettensatz is used. Thus just try both, with the various options, before concluding that you cannot solve your favorite system with zeroSetSplit. There exist more options at the development level that are not currently available in this public version.

9.67 RegularTriangularSet¶

Previous topic

Next topic

This Page