Overview of the RegularChains[SemiAlgebraicSetTools] Subpackage of RegularChains

Calling Sequence


RegularChains[SemiAlgebraicSetTools][command](arguments)
command(arguments)


Description


•

The RegularChains[SemiAlgebraicSetTools] subpackage contains a collection of commands for manipulating semialgebraic systems and their solution sets. A semialgebraic system is a set of equations, inequations and inequalities given by polynomials; the coefficients of those polynomials and the unknowns are all real numbers. A solution of such system is a point whose coordinates satisfy all these equations, inequations and inequalities simultaneously once the coordinates of this point replace the polynomial variables, according to a prescribed variable ordering.

•

For semialgebraic systems with finitely many solutions, the RegularChains[SemiAlgebraicSetTools] subpackage provides commands for isolating and counting the solutions of such systems. These commands can also be used for isolating and counting the real roots of zerodimensional regular chains (that is, regular chains with a finite number of complex solutions).

•

Each real root of a zerodimensional regular chain (or of a semialgebraic system with finitely many solutions) can be isolated using a socalled box, that is, a Cartesian product of singletons and open intervals. See the commands RealRootIsolate and BoxValues.

•

Two methods can be used for isolating real roots of zerodimensional regular chains and semialgebraic systems. The first one is a generalization of the VincentCollinsAkritas Algorithm which isolates real roots for univariate polynomials. The techniques are very close to the ones used by Renaud Rioboo in his ISSAC 1992 paper (see reference below). The other method implements the algorithm of the paper "An Algorithm for Isolating the Real Solutions of Semialgebraic Systems." by B. Xia and L. Yang.

•

The command RealRootCounting counts the number of solutions of a semialgebraic system with finitely many solutions.

•

The empty set is a special semialgebraic set which can be constructed by the command EmptyConstructibleSet.

•

An important tool provided by this package is a command for cylindrical algebraic decomposition. See the command CylindricalAlgebraicDecompose. In broad terms, for a given set of polynomials in n variables, this commands computes a partition of the ndimensional Euclidean space into regions, where the sign (negative, null or positive) of each of those polynomials does not change.

•

Another related tool is a command for partial cylindrical algebraic decomposition. See the command PartialCylindricalAlgebraicDecomposition. It computes only the maximal dimensional cells of the cylindrical algebraic decomposition induced by the input polynomials and represent each of which by a rational sample point. It can be used as a subroutine to decide whether a semialgebraic system with only strict positive inequalities has solutions or not. Together with the other commands of this package, it is an essential tool for studying the real solutions of polynomial systems, with or without parameters. For the parametric case, see the command RealRootClassification. For the nonparametric case, see the command RealTriangularize.

•

The output of RealTriangularize is a list of regular semialgebraic systems. A regular semialgebraic system is the adaptation of the notion of a regular chain to the purpose of computing the real solutions of a polynomial system, by means of triangular decomposition techniques. See the mathematical definitions below and the command RealTriangularize for details.

•

The command RemoveRedundantComponents returns a list of regular semialgebraic system whose zero sets are pairwise noninclusive. The input and output regular semialgebraic systems should have the same zero set.

•

The output of RealRootClassification is a pair consisting of a list of regular semialgebraic sets and a socalled border polynomial. Up to exceptional cases, a border polynomial is a list of polynomials. See the mathematical definitions below and the command BorderPolynomial for details.



Mathematical Definitions


•

A regular semialgebraic system of R is the data of a regular chain rc of R, a list P of polynomials of R (each of them defining a positive inequality) and a quantifierfree formula Q given by polynomials involving the free variables of rc only. In addition, the following three constraints are satisfied. First, each polynomial in P is regular w.r.t. the saturated ideal of rc. Second, Q defines a nonempty and open semialgebraic set C in the space of the free variables of rc. Third, if denotes the semialgebraic system whose equations are given by the polynomials of rc, whose positive inequalities are given by the polynomials of P and with no inequations, then admits real solutions at any point of C.


The zero set of the regular semialgebraic system given by rc, P and Q consists of all the zeros of that extend a point of C.

•

A regular semialgebraic set is an encoding for some (or all the) real solutions of a regular chain rc whose nonalgebraic variables are constrained in a nonempty semialgebraic set C such that rc separates well (that is, is delineable) and admits a positive constant number of real solutions at any point of C.


In theory, a regular semialgebraic set can always be defined as the union of zero sets of finitely many regular semialgebraic systems and vice versa. However, the first encoding is more suitable for certain algorithms such as the one of the RealRootClassification command. This encoding is described below.


When it is finite, a regular semialgebraic set can be encoded as a list of points with real coordinates. Each point is defined by a regular chain and a Cartesian product of isolation intervals. Such an encoding is called a numeric box (or simply a box). See the commands RealRootIsolate and BoxValues for more precise details.


When it is infinite, a regular semialgebraic set can be encoded by the data of a regular chain rc of R, a quantifierfree formula Q given by polynomials involving the free variables of rc and a root index list L (to be defined hereafter). In addition, the two following properties must hold. The quantifierfree formula Q defines a nonempty semialgebraic set C such that rc separates well (that is, is delineable) and admits a positive and constant number of real solutions at any point of C. As a consequence, you can index the real solutions of rc uniformly above C. This is where root index list L is introduced. It allows one to select some of the real roots of rc. Finally, the regular chain rc, the quantifierfree formula Q and the root index list L form a socalled parametric box.


A squarefree semialgebraic system of R is a squarefree regular system (as defined in ConstructibleSetTools) given by a regular chain rc of R and a polynomial set P such that each polynomial in P must be regular modulo the saturated ideal of rc, which itself must be radical. The zero set of this squarefree semialgebraic system consists of the real points of the quasicomponent of rc which make each polynomial in P strictly positive. The type squarefree_semi_algebraic_system is used for squarefree semialgebraic systems.


A semialgebraic set is any zero set of a semialgebraic system. Here semialgebraic system is understood as any finite disjunction of conjunction of polynomial equations, inequations and inequalities. The type semi_algebraic_set is used for semialgebraic sets. One possible representation is by regular semialgebraic systems. An alternative representation is by CAD cells.


A CAD cell of the ndimensional Euclidean space with coordinates x1 < ... < xn is defined recursively as follows. For n=1 it is either a point or an interval; in the first case x1 is set to an algebraic expression while in the second case x1 is strictly bounded between two algebraic expressions; in both cases each of these algebraic expressions is a RootOf expression where the defining polynomial is univariate over the rational numbers. For n>1 it is a CAD cell of the n1dimensional space together with a constraint on xn of type section or sector. In the first case xn is set to an algebraic expression and in the second xn is strictly bounded between two algebraic expressions; in both cases, each algebraic expression is a RootOf expression where the defining polynomial is univariate with coefficients that are polynomials in the previous coordinates.



List of RegularChains[SemiAlgebraicSetTools] Subpackage Commands



The following is a list of the available commands.



See Also


BorderPolynomial, Complement, CylindricalAlgebraicDecompose, Difference, Intersection, IsEmpty, IsParametricBox, LazyRealTriangularize, LinearSolve, module, PartialCylindricalAlgebraicDecomposition, PositiveInequalities, Projection, RealComprehensiveTriangularize, RealRootClassification, RealRootCounting, RealRootIsolate, RealTriangularize, RealTriangularize, RefineBox, RegularChains, RepresentingBox, RepresentingChain, RepresentingQuantifierFreeFormula, RepresentingRootIndex, SamplePoints, UsingPackages, VariableOrdering


References



F. Boulier, C. Chen, F. Lemaire, M. Moreno Maza "Real root isolation of regular chains." ASCM'09, MathforIndustry, Lecture Note Series Vol. 22 (2009): 1529.


C. Chen, J.H. Davenport, J. May, M. Moreno Maza, B. Xia, R. Xiao, Y. Xie "User interface design for geometrical decomposition algorithms in Maple." MathUI'09.


C. Chen, J.H. Davenport, J. May, M. Moreno Maza, B. Xia, R. Xiao "Triangular Decomposition of semialgebraic systems." ISSAC'10, , ACM Press, 2010.


C. Chen, J.H. Davenport, M. Moreno Maza, B. Xia, R. Xiao "Computing with semialgebraic sets represented by triangular decomposition". ISSAC'11, , ACM Press, 2011.


C. Chen, M. Moreno Maza, B. Xia, L. Yang "Computing cylindrical algebraic decomposition via triangular decomposition." ISSAC'09, ACM Press, 2009.


C. Chen, and M. Moreno Maza. "Semialgebraic description of the equilibria of dynamical systems." Proc. Cof the 2011 International Workshop on Computer Algebra in Scientific Computing (CASC 2011), LNCS Vol. 6885: 101125. Springer, 2011.


R. Rioboo. "Computation of the real closure of an ordered field." ISSAC'92, Academic Press, San Francisco.


L. Yang, X. Hou, B. Xia. "A complete algorithm for automated discovering of a class of inequalitytype theorems." Sci. China Ser. F, Vol. 44 (2001): 3349.


B. Xia, L. Yang. "An Algorithm for Isolating the Real Solutions of Semialgebraic Systems." J. Symb. Comput. , Vol. 34 No. 5 (2002): 461477.


