Studying and solving polynomial systems with the RegularChains library
Parisa Alvandi, Changbo Chen, James Davenport, Juergen Gerhard, Mahsa Kazemi, Francois Lemaire, Liyun Li, Xin Li, John May, Marc Moreno Maza, Wei Pan, Bican Xia, Rong Xiao, and Yuzhen Xie
1. Introduction
The RegularChains library offers a variety of commands for solving polynomial systems symbolically and studying their solutions. The input systems may contain polynomial equations p=0, polynomial inequations p≠0, and polynomial inequalities p>0 or p≥0. All of those may be nonlinear. For a given system, the coefficients of the input polynomials may be rational numbers, integers modulo a prime, or polynomials depending on parameters. The solution sets computed by the RegularChains library are described by lists of components. Geometrically, such a component can be a point (or a set of points), a curve (or a set of curves), a surface (or a set of surfaces), etc. Computationally, components are represented by a special kind of polynomial system with a triangular shape and other algebraic properties. Depending if the input system consists of equations only, has inequations but no inequalities, or possesses inequalities, the system representing a component is called a regular chain, a regular system or a regular semi-algebraic system, respectively. The word "regular" refers to the interesting algebraic properties that these systems have. The RegularChains library provides types for these different kinds of polynomial systems; this important feature will be illustrated hereafter.
Another design feature of the RegularChains library is the organization of its 146 commands into 8 modules. The top-level of the library gathers the most commonly used commands, whereas the six submodules are dedicated to special topics. The submodules ChainTools, ConstructibleSetTools, and SemiAlgebraicSetTools deal respectively with specific operations on regular chains, regular systems, and regular semi-algebraic systems. The submodule MatrixTools allows the user to handle linear systems over domains with zero-divisors. This is a fundamental tool in the theory of regular chains with many potential applications. The AlgebraicGeometryTools submodule provides facilities for studying algebraic curves, surfaces and algebraic sets of higher dimension.
The submodule ParametricSystemTools is devoted to solving systems with parameters, including real root classification and complex root classification of such systems, as demonstrated below. Finally, the submodule FastArithmeticTools provides highly optimized implementation of some fundamental operations on regular chains, similar to some commands of the top-level module and ChainTools. However, the commands of this submodule can only be used under some assumptions and their usage requires care and advanced knowledge.
restart; with(RegularChains); with(ChainTools); with(MatrixTools); with(ConstructibleSetTools); with(ParametricSystemTools); with(SemiAlgebraicSetTools); with(FastArithmeticTools); with(AlgebraicGeometryTools);
AlgebraicGeometryTools,ChainTools,ConstructibleSetTools,Display,DisplayPolynomialRing,Equations,ExtendedRegularGcd,FastArithmeticTools,Inequations,Info,Initial,Intersect,Inverse,IsRegular,LazyRealTriangularize,MainDegree,MainVariable,MatrixCombine,MatrixTools,NormalForm,ParametricSystemTools,PolynomialRing,Rank,RealTriangularize,RegularGcd,RegularizeInitial,SamplePoints,SemiAlgebraicSetTools,Separant,SparsePseudoRemainder,SuggestVariableOrder,Tail,Triangularize
Chain,ChangeOfCoordinates,ChangeOfOrder,Construct,Cut,DahanSchostTransform,Dimension,Empty,EqualSaturatedIdeals,EquiprojectableDecomposition,Extend,ExtendedNormalizedGcd,IsAlgebraic,IsEmptyChain,IsInRadical,IsInSaturate,IsIncluded,IsPrimitive,IsStronglyNormalized,IsZeroDimensional,IteratedResultant,LastSubresultant,Lift,ListConstruct,NormalizeRegularChain,NumberOfSolutions,Polynomial,Regularize,RemoveRedundantComponents,SeparateSolutions,Squarefree,SquarefreeFactorization,SubresultantChain,SubresultantOfIndex,Under,Upper
IsZeroMatrix,JacobianMatrix,LowerEchelonForm,MatrixInverse,MatrixMultiply,MatrixOverChain
Complement,ConstructibleSet,CylindricalDecompose,Difference,EmptyConstructibleSet,GeneralConstruct,Intersection,IsContained,IsEmpty,MakePairwiseDisjoint,PolynomialMapImage,PolynomialMapPreimage,Projection,QuasiComponent,RationalMapImage,RationalMapPreimage,RefiningPartition,RegularSystem,RegularSystemDifference,RepresentingChain,RepresentingInequations,RepresentingRegularSystems,SeparateZeros,Union
BelongsTo,BorderPolynomial,CoefficientsInParameters,ComplexRootClassification,ComprehensiveTriangularize,DefiningSet,DiscriminantSequence,DiscriminantSet,PreComprehensiveTriangularize,RealComprehensiveTriangularize,RealRootClassification,Specialize
BoxValues,Complement,CylindricalAlgebraicDecompose,Difference,DisplayParametricBox,DisplayQuantifierFreeFormula,EmptySemiAlgebraicSet,Intersection,IsContained,IsEmpty,IsParametricBox,LinearSolve,PartialCylindricalAlgebraicDecomposition,PositiveInequalities,Projection,QuantifierElimination,RealRootCounting,RealRootIsolate,RefineBox,RefineListBox,RemoveRedundantComponents,RepresentingBox,RepresentingChain,RepresentingQuantifierFreeFormula,RepresentingRootIndex,SignAtBox,VariableOrdering
BivariateModularTriangularize,IteratedResultantDim0,IteratedResultantDim1,NormalFormDim0,NormalizePolynomialDim0,NormalizeRegularChainDim0,RandomRegularChainDim0,RandomRegularChainDim1,ReduceCoefficientsDim0,RegularGcdBySpecializationCube,RegularizeDim0,ResultantBySpecializationCube,SubresultantChainSpecializationCube
Cylindrify,IntersectionMultiplicity,IsTransverse,LimitPoints,RationalFunctionLimit,RegularChainBranches,TangentCone,TangentPlane,TriangularizeWithMultiplicity
2. Polynomial systems and regular chains
This section introduces the user to the top-level module of the RegularChains library. The concept of a regular chain is based on a recursive and univariate vision of a polynomial. Several commands manipulating polynomials in this manner are illustrated below. The most commonly used command of the library is called Triangularize and is illustrated by several examples. It takes a polynomial system as input and returns a description of its solution set. If the input system consists of equations only, then this description is a list of regular chains. The case where the input system admits inequations can be handled by Triangularize or by the command GeneralConstruct of the ConstructibleSetTools submodule. In case of inequalities, and more generally for computing the real solutions of a polynomial system, the commands RealTriangularize, LazyRealTriangularize and SamplePoints of the top-level module can be used. Different commands are also available in the modules ParametricSystemTools and SemiAlgebraicSetTools for the same purpose of real solving but for particular types of systems: they will be presented later in this document.
2.1 A univariate vision of polynomials
Define the polynomial ring ℚx,y,z with the variable ordering x>y>z. The field ℚ of rational numbers is the default coefficient ring.
R := PolynomialRing([x, y, z]);
R≔polynomial_ring
The internal representation of this polynomial ring can be accessed as follows.
Display(R);
Variables:⁢x,y,zParameters:⁢∅Characteristic:⁢0
Consider the following polynomial.
p := (y+1)*x^3+(z+4)*x+3;
p≔y+1⁢x3+z+4⁢x+3
The main variable of p as a polynomial of R is given by:
y+1⁢x3+z+4⁢x+3
polynomial_ring
MainVariable(p, R);
x
The initial (or leading coefficient) of p:
Initial(p, R);
y+1
The degree of p in the main variable:
MainDegree(p, R);
3
The rank of p, which is the main variable of p raised to the main degree of p:
Rank(p, R);
x3
The tail of p.
Tail(p, R);
x⁢z+4⁢x+3
The separant of p, which is the derivative of p with regards to its main variable:
Separant(p, R);
3⁢x2⁢y+3⁢x2+z+4
Change the ordering to z>y>x:
R := PolynomialRing([z, y, x]); Display(R); p := expand((y+1)*x^3+(z+4)*x+3); MainVariable(p, R); Initial(p, R); Rank(p, R); Tail(p, R); Separant(p, R);
Variables:⁢z,y,xParameters:⁢∅Characteristic:⁢0
p≔x3⁢y+x3+x⁢z+4⁢x+3
z
x3⁢y+x3+4⁢x+3
Consider the polynomial ring ℤ3z,y,x with the ordering z>y>x.
R := PolynomialRing([z, y, x], 3); Display(R); Initial(p, R); Tail(p, R);
Variables:⁢z,y,xParameters:⁢∅Characteristic:⁢3
x3⁢y+x3+x
2.2 Computing the subresultants of two polynomials
The command SubresultantChain in the ChainTools module is used to compute the subresultant chain of two polynomials. Let us illustrate this by an example.
Define a ring of polynomials.
R := PolynomialRing([y, x]);
Define two polynomials of R.
f1 := (y^2+6)*(x-1)-y*(x^2+1);
f1≔y2+6⁢x−1−y⁢x2+1
f2 := (x^2+6)*(y-1)-x*(y^2+1);
f2≔x2+6⁢y−1−x⁢y2+1
Compute their subresultant chain w.r.t the variable y
src := SubresultantChain(f1, f2, y, R);
src≔subresultant_chain
The result is of type subresultant_chain and encodes all the polynomials in the subresultant chain. To display the ith subresulant polynomial, one can call the command SubresultantOfIndex. For example, to know the subresultant of index 0, that is the resultant, one can do as follows
res := SubresultantOfIndex(0, src, R);
res≔2⁢x6−22⁢x5+102⁢x4−274⁢x3+488⁢x2−552⁢x+288
To display all the subresultant polynomials, one can call the command Display.
Display(src, R);
−x2+5⁢x−6⁢y−x3+6⁢x2−11⁢x+62⁢x6−22⁢x5+102⁢x4−274⁢x3+488⁢x2−552⁢x+288
The encoding of the subresultants can be controlled by an optional argument. This encoding can be by values, over the monomial basis or via the Bezout Matrix.
When this optional argument is not specified, the encoding is chosen according to a heuristical algorithm.
src := SubresultantChain(f1, f2, y, R, representation = BezoutMatrix); op(src);
table⁡SRC_MDEG=1,SRC_POLYQ=x2⁢y−x⁢y2−x2−x+6⁢y−6,representation=BezoutMatrix,SRC_MVAR=y,type=subresultant_chain,SRC_MATRIX=−x2+5⁢x−6−x3+6⁢x2−11⁢x+6−x3+6⁢x2−11⁢x+6x4−5⁢x3+13⁢x2−35⁢x+42,SRC_POLYP=−x2⁢y+x⁢y2−y2+6⁢x−y−6
src := SubresultantChain(f1, f2, y, R, representation = MonomialBasis); op(src);
table⁡SRC_MDEG=1,SRC_POLYQ=x2⁢y−x⁢y2−x2−x+6⁢y−6,representation=MonomialBasis,SRC_MVAR=y,subresultant_chain_vector=2⁢x6−22⁢x5+102⁢x4−274⁢x3+488⁢x2−552⁢x+288,−x3−x2⁢y+6⁢x2+5⁢x⁢y−11⁢x−6⁢y+6,x2⁢y−x⁢y2−x2−x+6⁢y−6,−x2⁢y+x⁢y2−y2+6⁢x−y−6,type=subresultant_chain,SRC_POLYP=−x2⁢y+x⁢y2−y2+6⁢x−y−6
2.3 Solving systems of equations with regular chains
Define a set of polynomials of R.
sys := {x+y+z^2-1, x+y^2+z-1, x^2+y+z-1};
sys≔z2+x+y−1,y2+x+z−1,x2+y+z−1
Ideally, one would like to decompose the solutions of sys into a list of points. This is what the command Triangularize does using symbolic expressions. In the output decomposition, some points are grouped because they share some properties. These groups are called regular chains.
A regular chain is a system of equations and inequations, satisfying special algebraic properties. First, the equation part consists of non-constant polynomials with pairwise different main variables; thus, the equation part has a triangular shape. Second, the inequation part consists of the initials of the polynomials defining the equations; moreover, the product of those initials is regular (that is, not a zero-divisor) modulo the saturated ideal of the equation part. This technical condition can be skipped by the non-expert reader, since in most practical examples the inequations are trivial and can be ignored. This is the case in our example where all initials are equal to 1, leading to trivial inequations.
l := Triangularize(sys, R);
l≔regular_chain,regular_chain,regular_chain,regular_chain
map(Equations, l, R); map(Inequations, l, R); map(NumberOfSolutions, l, R);
x−z,y−z,z2+2⁢z−1,x,y,z−1,x,y−1,z,x−1,y,z
∅,∅,∅,∅
2,1,1,1
The result is to be interpreted as follows: The system sys is equivalent to a union of four regular chains. The equations for the first such regular chain are x−1=y=z=0, the equations for the second regular chain are x=y−1=z=0, etc. None of the four regular chains have any inequations. The first three regular chains have exactly one solution, and the last one has two solutions.
Note that you can also specify inequations of the form p≠0. For example, you can specify that x−z must not vanish.
l := Triangularize(sys, [x-z], R); map(Equations, l, R); map(NumberOfSolutions, l, R);
l≔regular_chain,regular_chain
x−1,y,z,x,y,z−1
1,1
2.4 Solving polynomial systems with infinitely many solutions
In the previous examples, the polynomial systems have finitely many solutions. To illustrate how the Triangularize command handles systems with infinitely many solutions, consider the following parametric linear system with unknowns x,y and parameters a,b,c,d,g,h.
R := PolynomialRing([x, y, a, b, c, d, g, h]); sys := {a*x+b*y-g, c*x+d*y-h};
sys≔a⁢x+b⁢y−g,c⁢x+d⁢y−h
By default, the Triangularize command computes the generic solutions of the input system. For this parametric linear system, this implies its determinant is assumed to be nonzero.
l := Triangularize(sys, R); map(Equations, l, R); map(Inequations, l, R);
l≔regular_chain
c⁢x+y⁢d−h,a⁢d−b⁢c⁢y−a⁢h+c⁢g
c,d⁢a−b⁢c
Thus, the resulting regular chain consists of the two equations c x+d y−h=a d−b cy+c g−a h=0 and the two inequations c≠0≠a d−b c, the first of which reflects the choice of c as a pivot.
The other available Maple commands for solving such a system do a similar job.
solve(sys, {x, y});
x=−b⁢h−d⁢gd⁢a−b⁢c,y=a⁢h−c⁢gd⁢a−b⁢c
Groebner[Solve](sys, {x, y});
d⁢x⁢a−b⁢c⁢x+b⁢h−d⁢g,y⁢a⁢d−y⁢b⁢c−a⁢h+c⁢g,plex⁡y,x,∅
The Triangularize command can do more if the option "output=lazard" is used. In this case, all the solutions of the input are computed, generic or not. This implies that the case where the determinant vanishes is also considered and solved. For each regular chain below, its equations and inequations are printed.
l := Triangularize(sys, R, output = lazard): seq(Display(l[i], R), i = 1..nops(l));
c⁢x+d⁢y−h=0d⁢a−b⁢c⁢y−h⁢a+c⁢g=0d⁢a−b⁢c≠0c≠0,c⁢x+d⁢y−h=0d⁢a−b⁢c=0h⁢b−d⁢g=0c≠0d≠0h≠0,a⁢x+b⁢y−g=0d⁢y−h=0c=0a≠0d≠0,d⁢y−h=0a=0h⁢b−d⁢g=0c=0d≠0h≠0,c⁢x−h=0h⁢a−c⁢g=0b=0d=0c≠0h≠0,a⁢x+b⁢y−g=0c=0d=0h=0a≠0,c⁢x+d⁢y=0d⁢a−b⁢c=0g=0h=0c≠0d≠0,b⁢y−g=0a=0c=0d=0h=0b≠0,y=0a=0c=0g=0h=0,x=0b=0d=0g=0h=0,a=0b=0c=0d=0g=0h=0
One may also want to "push" some parameters into the field of coefficients, that is, to solve over a field of rational functions. Consider a new polynomial ring over the field ℚg,h of rational functions in g and h.
R2≔PolynomialRingx,y,a,b,c,d,g,h:l≔Triangularizesys,R2,output=lazard: seqDisplayli, R2, i=1..nopsl;
c⁢x+d⁢y−h=0d⁢a−b⁢c⁢y−h⁢a+c⁢g=0d⁢a−b⁢c≠0c≠0,c⁢x+d⁢y−h=0d⁢a−b⁢c=0h⁢b−d⁢g=0c≠0d≠0,a⁢x+y⁢b−g=0d⁢y−h=0c=0a≠0d≠0,d⁢y−h=0a=0h⁢b−d⁢g=0c=0d≠0,c⁢x−h=0h⁢a−c⁢g=0b=0d=0c≠0
Finally, we solve over ℤ3g,h, that is, over the field of rational functions in g and h modulo 3.
R3:=PolynomialRing⁡x,y,a,b,c,d,g,h,3;l:=Triangularize⁡sys,R3,output=lazard;opDisplayl, R3;
R3≔polynomial_ring
l≔regular_chain,regular_chain,regular_chain,regular_chain,regular_chain
c⁢x+d⁢y+2⁢h=0d⁢a+2⁢b⁢c⁢y+2⁢h⁢a+c⁢g=0d⁢a+2⁢b⁢c≠0c≠0,c⁢x+d⁢y+2⁢h=0d⁢a+2⁢b⁢c=0h⁢b+2⁢d⁢g=0c≠0d≠0,a⁢x+y⁢b+2⁢g=0d⁢y+2⁢h=0c=0a≠0d≠0,d⁢y+2⁢h=0a=0h⁢b+2⁢d⁢g=0c=0d≠0,c⁢x+2⁢h=0h⁢a+2⁢c⁢g=0b=0d=0c≠0
2.5 Regular chains and polynomial gcds
The main subroutine of the Triangularize command is the RegularGcd command, which computes polynomial gcds modulo regular chains. This routine is illustrated hereafter together with basic commands on regular chains from the ChainTools submodule.
Here's the empty regular chain and its internal representation.
Empty(R); op(Empty(R));
regular_chain
property,polynomials,type,ModulePrint,moduleoptionrecord;exportproperty,polynomials,type,ModulePrint;end module
You can construct a new regular chain by adding a (suitable) polynomial p to an existing regular chain T. This operation may return a list of regular chains. Indeed, checking that the initial of p is regular with regards to (the saturated ideal of) T may split T.
On the example below, this does not happen; the regular chain T is empty.
l := Construct(x^2+1, Empty(R), R); rc := l[1];
rc≔regular_chain
The internal representation of the new regular chain rc is as follows. For each polynomial in the regular chain, the data structure stores its main variable, its main degree, and its initial. These quantities are needed quite frequently and are therefore cached to avoid recomputing them each time they are needed.
The internal representation also shows a property about the regular chain: isPrime. This means that its saturated ideal is a prime ideal. The knowledge of such property helps to speed up computations.
op(rc);
Now compute the greatest common divisor of two polynomials p1and p2modulo rc. The example is designed such that y+1 is a gcd.
p1:=expand⁡x+1⋅y+x⋅y+1;p2≔expandx−1⋅y+x⋅y+1;
p1≔x⁢y2+2⁢x⁢y+y2+x+y
p2≔x⁢y2+2⁢x⁢y−y2+x−y
In general, the output of a gcd computation modulo a regular chain is a list of "cases".
In the above example, no case splits can happen since rc defines a field. However, note that the output, below, is not exactly the one expected.
rg:=RegularGcd⁡p1,p2,y,rc,R;factor⁡rg11
rg≔2⁢x⁢y+2⁢x,regular_chain
2⁢x⁢y+1
However, the extraneous factor 2 x is a unit modulo rc. Thus, the expected and the computed gcds are in fact associate, and therefore the result is correct.
Consider an example where a split is necessary during a gcd computation. To create such an example, you need to make sure that the input equations do not factor, because otherwise the Construct command will already split the system. The example below has three variables; the two variables x and y are used for building a regular chain with two polynomials mx and my.
R := PolynomialRing([z, y, x]);
The first polynomial is irreducible over <.
mx := x^2-2;
mx≔x2−2
Thus, constructing a regular chain from it produces a single output. Make a copy of it for later use.
rc := Construct(mx, Empty(R), R)[1]; rcx := rc;
rcx≔rc
The Construct command has detected that (the saturated ideal of) rc is a prime ideal.
The second polynomial is not irreducible in ℚxy. The Construct command would easily discover this fact and would split it when constructing a regular chain involving rc.
my := expand((y-x)*(y+x-1));
my≔−x2+y2+x−y
By reducing my modulo rc, the reduced polynomial becomes irreducible in ℚxy.
my := SparsePseudoRemainder(my, rc, R);
my≔y2+x−y−2
Extend rc by my.
l := Construct(my, rc, R);rc := l[1];
The Construct command uses inexpensive criteria to detect whether the associated saturated ideal is prime or not. These criteria fail here. So the constructed regular chain rc has no particular properties.
op(rc);Equations(rc, R);
y2−y+x−2,x2−2
Compute the gcd of p1 and p2, defined below, modulo rc.
p1≔y−x⁢z+x+y−1⁢z+1;p2≔y−x+x+y−1⁢z+1
p1≔y−x⁢z+y+x−1⁢z+1
p2≔y−x+y+x−1⁢z+1
The example is constructed in such a way that splitting is needed: modulo the first factor of my, namely y−x, the gcd is z+1, while it is constant modulo the second factor, y+x−1. Correspondingly, there are two branches.
rg:=RegularGcd⁡p1,p2,z,rc,R;
rg≔y+x−1⁢z+2⁢y−1,regular_chain,3⁢y2+−2⁢x−2⁢y−x2+2⁢x,regular_chain
Check the first case.
g1,rc1≔oprg1;eq1:=Equations⁡rc1,R;SparsePseudoRemainder⁡2⁢x+1⁢eq11,rcx,R
g1,rc1≔y+x−1⁢z+2⁢y−1,regular_chain
eq1≔2⁢x−1⁢y+x−4,x2−2
−7⁢x+7⁢y
Note that rc1 is not normalized. The SparsePseudoRemainder computation shows that it corresponds to the "modulo y−x" branch.
u:=SparsePseudoRemainder⁡g1,rc1,R;factoru
u≔−4⁢z⁢x−4⁢x+9⁢z+9
−z+1⁢4⁢x−9
This is the desired result, up to a multiplicative factor −4⁢x+9 which is a unit modulo rc1.
Check the second case. Again, the regular chain rc2 is not normalized, and the SparsePseudoRemainder computation shows that it corresponds to the "modulo y+x−1" branch.
g2,rc2≔oprg2;eq2≔Equationsrc2,R;SparsePseudoRemainder2⁢x+1⁢eq21,rcx,R
g2,rc2≔3⁢y2+−2⁢x−2⁢y−x2+2⁢x,regular_chain
eq2≔2⁢x−1⁢y−3⁢x+5,x2−2
7⁢x+7⁢y−7
Check that g2 is a unit modulo rc2. First, reduce it modulo rc2. Then ask if the result is invertible modulo rc2. The answer proves it is.
h:=SparsePseudoRemainder⁡g2,rc2,R;out:=Inverse⁡h,rc2,R;ih:=out111;SparsePseudoRemainderh⁢ih,rc2,R
h≔−72⁢x+113
out≔113+72⁢x,2401,regular_chain,
ih≔113+72⁢x
2401
2.6 Solving systems of equations incrementally
The central command of the RegularChains library is the Triangularize command. The algorithm behind this command solves systems of equations incrementally. To do this, we rely on an important operation Intersect, which computes the common part of a hypersurface and the quasi-component of a regular chain. See the help page of Intersect for a more formal description of it. Let us now illustrate how to use it to solve a polynomial system incrementally.
vars := [x, y, z];R := PolynomialRing(vars);
vars≔x,y,z
Define a set of equations.
sys := [x^2+y+z-1, x+y^2+z-1, x+y+z^2-1];
sys≔x2+y+z−1,y2+x+z−1,z2+x+y−1
Define the empty regular chain.
rc := Empty(R);
Solve the first equation.
dec := Intersect(sys[1], rc, R);map(Equations, dec, R);
dec≔regular_chain
x2+y+z−1
Solve the first and second equations.
dec := [seq(op(Intersect(sys[2], rc, R)), `in`(rc, dec))];map(Equations, dec, R);
dec≔regular_chain,regular_chain
x−y,y2+y+z−1,x+y−1,y2−y+z
Solve the three equations together.
dec := [seq(op(Intersect(sys[3], rc, R)), `in`(rc, dec))];Display(dec, R);
dec≔regular_chain,regular_chain,regular_chain,regular_chain
x−z=0y−z=0z2+2⁢z−1=0,x=0y=0z−1=0,x−1=0y=0z=0,x=0y−1=0z=0
3. Real solutions of polynomial systems
The RegularChains library offers a variety of tools to compute the real solutions of polynomial systems. A first group of commands (namely RealTriangularize, LazyTriangularize and SamplePoints) deals with arbitrary semi-algebraic systems. That is, given any system S of polynomial equations, polynomial inequations and polynomial inequalities (strict or large) these commands produce information about the real solutions of this system.
RealTriangularize returns a full description of the real solutions of S: it computes simpler systems S1,...,Se such that a point is a solution of S if and only if it is a solution of one of the systems S1,...,Se. Each of these systems
has a triangular shape and remarkable properties: for this reason it is called a regular semi-algebraic system and the set of the S1,...,Se is called a full triangular decomposition of S.
LazyRealTriangularize allows the user to compute a triangular decomposition of S in an interactive manner. This feature is particularly well adapted for systems that are hard to solve. For such systems, LazyRealTriangularize returns the components of S of maximum dimension together with unevaluated recursive calls, such that, when fully evaluated, these calls produce the other components of S (which are generally harder to compute).
SamplePoints is even a lazier (and thus much cheaper) way of solving:
it produces at least one sample point per connected component
of the solution set of S. This way of solving is often sufficient in practical problems.
A second group of commands compute the real solutions of particular
types of polynomial systems (such as systems with finitely many complex solutions or parametric systems) or provide advanced features (such as CylindricalAlgebraicDecompose, LinearSolve, Projection, Difference). All these commands except RealRootClassification and RealComprehensiveTriangularize are located in the subpackage SemiAlgebraicSetTools.
3.1 RealTriangularize: solving systems of equations, inequations and inequalities
Consider the generic equation of degree two.
R := PolynomialRing([x, c, b, a]); sys := [a*x^2+b*x+c=0];
sys≔a⁢x2+b⁢x+c=0
Compute a triangular decomposition of the 4-variable hypersurface it defines.
dec := RealTriangularize(sys, R);
dec≔regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system
Display(dec, R);
a⁢x2+b⁢x+c=0−4⁢c⁢a+b2>0anda≠0,2⁢a⁢x+b=04⁢a⁢c−b2=0a≠0,b⁢x+c=0a=0b≠0,c=0b=0a=0
Consider the record output format.
RealTriangularize(sys, R, output=record);
a⁢x2+b⁢x+c=0−4⁢c⁢a+b2>0a≠0,2⁢a⁢x+b=04⁢a⁢c−b2=0a≠0,b⁢x+c=0b≠0a=0,c=0b=0a=0
Next, we consider a system of equations, inequations and inequalities.
R := PolynomialRing([y, x, b, a]);
sys := [x^3-3*y^2*x+a*x+b=0, 3*x^2-y^2+a=0, 1-y*x>0, y<>0];
sys≔x3−3⁢y2⁢x+a⁢x+b=0,3⁢x2−y2+a=0,0<−y⁢x+1,y≠0
out := RealTriangularize(sys, R);
out≔regular_semi_algebraic_system,regular_semi_algebraic_system
Display(out, R);
y2−3⁢x2−a=08⁢x3+2⁢a⁢x−b=0−y⁢x+1>04⁢a3+27⁢b2>0and4⁢b2⁢a3−16⁢a4+27⁢b4−512⁢a2−4096≠0,x⁢y+1=02⁢a3+18⁢b2+32⁢a⁢x+−a2−48⁢b=027⁢b4+4⁢a3⁢b2−16⁢a4−512⁢a2−4096=0
Consider now an example which has finitely many complex solutions.
R := PolynomialRing([x, y, z]):
sys := [x^3 + y + z -1=0, x + y^3 + z -1=0, x + y + z^3 -1=0];
sys≔x3+y+z−1=0,y3+x+z−1=0,z3+x+y−1=0
Compute the real solutions of sys.
dec≔regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system
x−z=0y−z=0z3+2⁢z−1=0,x−1=0y+1=0z−1=0,x=0y=0z−1=0,x+1=0y−1=0z−1=0,x−1=0y=0z=0,x=0y−1=0z=0,x−1=0y−1=0z+1=0
Returning now to systems which have infinitely many complex solutions, consider now the intersection of the algebraic surfaces Sofa and Cylinder from the Algebraic Surface Gallery. As their names suggest, they are respectively the equations of a sofa and a (sort of) cylinder. One expects to find a real curve in their intersection, as we shall verify.
R := PolynomialRing([z, y, x]); Sofa := x^2 + y^3 + z^5; Cyl := x^4 + z^2 - 1;
Sofa≔z5+y3+x2
Cyl≔x4+z2−1
RealTriangularize([Sofa, Cyl], R, output=record);
x8−2⁢x4+1⁢z+y3+x2=0y6+2⁢x2⁢y3+x20−5⁢x16+10⁢x12−10⁢x8+6⁢x4−1=0x<1x+1>0x12−4⁢x8+5⁢x4−1≠0,x8−2⁢x4+1⁢z−x2=0y3+2⁢x2=0x12−4⁢x8+5⁢x4−1=0,x8−2⁢x4+1⁢z+x2=0y=0x12−4⁢x8+5⁢x4−1=0,z=0y+1=0x+1=0,z=0y+1=0x−1=0
3.2 LazyRealTriangularize: interactive solving for systems of equations, inequations and inequalities
Consider again the generic equation of degree two. Now we solve it interactively.
sys≔x2⁢a+x⁢b+c=0
Use LazyRealTriangularize to start the decomposition.
dec := LazyRealTriangularize(sys, R);
dec≔a⁢x2+b⁢x+c=00<−4⁢c⁢a+b2∧a≠0LazyRealTriangularize⁡a=0,a⁢x2+b⁢x+c=0,polynomial_ringa=0LazyRealTriangularize⁡−4⁢c⁢a+b2=0,a⁢x2+b⁢x+c=0,polynomial_ring−4⁢c⁢a+b2=0otherwise
Go one step further, computing components in lower dimension.
dec2 := value(dec);
dec2≔x2⁢a+x⁢b+c=00<−4⁢a⁢c+b2∧a≠0x⁢b+c=0,a=0b≠0LazyRealTriangularize⁡a=0,b=0,x⁢b+c=0,x2⁢a+x⁢b+c=0,polynomial_ringb=0a=02⁢a⁢x+b=0,4⁢a⁢c−b2=0a≠0LazyRealTriangularize⁡a=0,−4⁢a⁢c+b2=0,4⁢a⁢c−b2=0,2⁢a⁢x+b=0,x2⁢a+x⁢b+c=0,polynomial_ringa=0−4⁢a⁢c+b2=0otherwise
Go the last step, computing components in dimension zero.
value(dec2);
x2⁢a+x⁢b+c=00<−4⁢a⁢c+b2∧a≠0x⁢b+c=0,a=0b≠0c=0,b=0,a=0b=0a=02⁢a⁢x+b=0,4⁢a⁢c−b2=0a≠0c=0,b=0,a=0a=0−4⁢a⁢c+b2=0otherwise
If one is only interested in computing the main components, the list output format does the job.
dec := LazyRealTriangularize(sys, R, output=list);
dec≔regular_semi_algebraic_system
a⁢x2+b⁢x+c=0−4⁢c⁢a+b2>0anda≠0
Another way to conduct the computation interactively is to use the record output format.
dec := [LazyRealTriangularize(sys, R, output=record)];
dec≔a⁢x2+b⁢x+c=0−4⁢c⁢a+b2>0a≠0,LazyRealTriangularize⁡a=0,a⁢x2+b⁢x+c=0,polynomial_ring,output=record,LazyRealTriangularize⁡−4⁢c⁢a+b2=0,a⁢x2+b⁢x+c=0,polynomial_ring,output=record
Go one step further.
dec2≔a⁢x2+b⁢x+c=0−4⁢c⁢a+b2>0a≠0,b⁢x+c=0b≠0a=0,LazyRealTriangularize⁡a=0,b=0,b⁢x+c=0,a⁢x2+b⁢x+c=0,polynomial_ring,output=record,2⁢a⁢x+b=04⁢a⁢c−b2=0a≠0,LazyRealTriangularize⁡a=0,−4⁢a⁢c+b2=0,4⁢a⁢c−b2=0,2⁢a⁢x+b=0,a⁢x2+b⁢x+c=0,polynomial_ring,output=record
Go the last step.
a⁢x2+b⁢x+c=0−4⁢a⁢c+b2>0a≠0,b⁢x+c=0b≠0a=0,c=0b=0a=0,2⁢a⁢x+b=04⁢a⁢c−b2=0a≠0,c=0b=0a=0
Computing a lazy triangular decomposition is usually much less expensive than computing a full one. The following is an example.
unassign('u'); variables := [x, u, v, w]; R := PolynomialRing(variables); sys := [u*x^2+v*x+1=0, v*x^3+w*x+u=0, w*x^2+v*x+u<=0];
variables≔x,u,v,w
sys≔u⁢x2+v⁢x+1=0,v⁢x3+w⁢x+u=0,w⁢x2+v⁢x+u≤0
Computing a lazy decomposition takes than a second.
dec := LazyRealTriangularize(sys,R,output=list);
Computing a full one does not terminate within an hour.
3.3 SamplePoints: computing at least one point per connected component
Consider again the generic equation of degree two.
R := PolynomialRing([x, c, b, a]); F := [a*x^2+b*x+c=0];
F≔a⁢x2+b⁢x+c=0
Compute sample points of the 4-variable hypersurface it defines.
S := SamplePoints(F, R, output=record);
S≔x=−1c=12b=0a=−12,x=1c=12b=0a=−12,x=−1c=−12b=0a=12,x=1c=−12b=0a=12,x=0c=0b=−12a=0,x=0c=0b=12a=0,x=0c=0b=0a=0,x=0c=0b=0a=−12,x=0c=0b=0a=12
Consider the Tacnode curve. We look for sample points in the middle of the right branch.
R := PolynomialRing([y, x]); F := [y^4-2*y^3+y^2-3*x^2*y+2*x^4];
F≔2⁢x4+y4−3⁢x2⁢y−2⁢y3+y2
with(plots): implicitplot(F, x=-2..2, y=-1..3, numpoints=1000000);
SamplePoints([op(F), 2*x > 1, x < 1], R, output=record);
y=1332,105256x=34,y=237128,11964x=34
3.4 Isolating the real roots of a regular chain
Isolating real roots
Define a simple regular chain.
R := PolynomialRing([y, x]): rc := Chain([2*x^2-1, 3*y^3-x], Empty(R), R):
Isolate its real roots.
rr := RealRootIsolate(rc, R);
rr≔box,box
Display the box values.
solution := map(BoxValues, rr, R);
solution≔y=−2072707333554432,−2072706333554432,x=−4634165536,−7414551048576,y=1036353116777216,1036353716777216,x=7414551048576,4634165536
Each element of the list is called a box. Each box encodes a real root, in the sense that it contains exactly one real root of rc. The RealRootIsolate command returns all real roots of a given regular chain in this way. Thus, it is guaranteed that no root is lost. In the example, there are two real roots.
solution[1]; solution[2];
y=−2072707333554432,−2072706333554432,x=−4634165536,−7414551048576
y=1036353116777216,1036353716777216,x=7414551048576,4634165536
Thus, the first root satisfies 12<x<1 and 0<y<1, and the second one satisfies −1<x<−12 and −1<x<0.
The BoxValues command returns a list of the form v=i, where v is a variable and i is either a rational number or an open interval encoded by a list. The reason why singletons are returned is that rational solutions are sometimes hit, as in the following example.
rc := Chain([2*x-1, 3*y^3-x], Empty(R), R): rr := RealRootIsolate(rc, R): map(BoxValues, rr, R);
y=5770531048576,288527524288,x=12
The Display command prints the isolated real roots in a pretty manner.
Display(rr, R);
y=5770531048576,288527524288x=12
Choosing a precision
The isolating boxes can be as small as needed. The abserr option allows you to obtain boxes whose widths are smaller than or equal to a certain absolute precision.
rc := Chain([2*x^2-1, 3*y^3-x], Empty(R), R): rr := RealRootIsolate(rc, R, abserr = 1/10^10): map(BoxValues, rr, R);
y=−27167378515774398046511104,−1086695140626917592186044416,x=−7592501251073741824,−97184015999137438953472,y=27167378515674398046511104,27167378515774398046511104,x=97184015999137438953472,7592501251073741824
evalf(%);
y=−0.6177146705,−0.6177146705,x=−0.7071067812,−0.7071067812,y=0.6177146705,0.6177146705,x=0.7071067812,0.7071067812
In fact, this involves the algebraic numbers 12 and 12313.
evalf⁡12;evalf⁡12313;
0.7071067810
0.6177146705
3.5 Isolating and counting the real zeros of a semi-algebraic system with finitely many solutions
Recall that a semi-algebraic system (SAS) is a system containing polynomial equations, polynomial (non-strict or/and strict) inequalities, and polynomial inequations, which are denoted by F, N, P, and H, respectively. For example, the system x2+y2−1=0, x y−1=0, x≥0, y>0 is represented by
F := [x^2+y^2-1, 2*x*y-1]: N := [x]: P := [y]: H := []:
Define the polynomial ring
R := PolynomialRing([x, y]):
The RealRootIsolate command isolates all the real zeros of a given semi-algebraic system.
rr := RealRootIsolate(F, N, P, H, R); solution := Display(rr, R);
rr≔box
solution≔x=58,34y=4564,91128
The RealRootCounting command computes the number of distinct real solutions of a given semi-algebraic system.
RealRootCounting(F, N, P, H, R);
1
Consider a less trivial example.
R := PolynomialRing([z, y, x, c]): F := [1-c*x-x*y^2-x*z^2, 1-c*y-y*x^2-y*z^2, 1-c*z-z*x^2-z*y^2, 8*c^6+378*c^3-27]: N := []: P := [c, 1-c]: H := []: RealRootCounting(F, N, P, H, R);
4
If the input system has infinitely many complex solutions (that is, it is positive-dimensional over the complex numbers), RealRootCounting will return a message suggesting to call RealRootClassification instead.
R := PolynomialRing([x, y]): RealRootCounting([x^2+y^2], [], [], [], R);
Error, (in RegularChains:-SemiAlgebraicSetTools:-RealRootCounting) system is not zero-dimensional; try RealRootClassification |lib/RegularChains/src/user.mm:9796|
3.6 Partial cylindrical algebraic decomposition
The command RealRootClassification makes use of Partial Cylindrical Algebraic Decomposition (PCAD). The calling sequence is PartialCylindricalAlgebraicDecomposition(p, lp, R), where R is a polynomial ring, p is a polynomial in R, and lp is a list of polynomials in R