Overview of the RegularChains Package
List of the RegularChains Package Commands
List of RegularChains Subpackages
The RegularChains package is a collection of commands for solving systems of algebraic equations, inequations and inequalities symbolically. This package also allows the user to manipulate and study the solutions of such systems.
The main two commands are Triangularize and RealTriangularize. Each of them computes from a system of polynomials S a list of simpler systems S1,...,Sn such that a point is a solution of S if and only if it is a solution of one of the systems S1,...,Sn. Each of these simpler systems S1,...,Sn is called a regular chain in the case of Triangularize and a regular semi-algebraic system in the case of RealTriangularize. In both cases, each of these simpler systems has a special shape and remarkable properties. We describe below the notion of a regular chain and refer to the page SemiAlgebraicSetTools for that of a regular semi-algebraic system.
To understand what a regular chain is, one first needs to define the input system S of Triangularize. It is assumed to be a list (or a set) of polynomials with coefficients in a field K and with variables from a set X. Typically, the field K is the set of the rational numbers. Call R the set of the polynomials with coefficients in K and variables in X. The set X is assumed to be totally ordered. Hence, when looking at a non-constant polynomial p of R, one can talk about its main (or greatest) variable, say v, and the leading coefficient of p with respect to v, called the initial of p.
Now we can describe the shape of a regular chain by defining a more general concept, sometimes called an ascending chain or a triangular set. A finite set T of non-constant polynomials of R is a triangular set if two different polynomials of T have different main variables. For example, if X consists of the two variables x and y such that y<x holds, then x−y+1,y2+1 is a triangular set, whereas x−y+1,y2−x is not. In broad words, a triangular set is a system of algebraic equations that is ready to be solved by evaluating the unknowns one after the other, just like a triangular linear system. However, there is a difference with the linear case: the back solving process may lead to some degenerated situation, or even to no solutions. Consider for example, for y<x, the triangular set y⁢x−1,y2−y. The value y=1 leads to x=1, but the value y=0 does not lead to a value of x. In broad words, regular chains are a particular kind of triangular sets for which the back solving process succeeds in every case. A precise definition of a regular chain is given below, just before the examples.
Regular chains have many interesting computational properties. One property is that it is very convenient to perform computations modulo a set of relations given by a regular chain. The set of relations that is naturally associated with a regular chain is called its saturated ideal. This concept is defined precisely below, just before the examples. When the regular chain T has as many polynomials as variables in X, then its saturated ideal is simply the ideal generated by T. The operations NormalForm and SparsePseudoRemainder are used intensively for computing modulo regular chains: they are used to simplify a polynomial with respect to a regular chain.
In addition to its main functions Triangularize and RealTriangularize, and its subpackages ChainTools, MatrixTools, ConstructibleSetTools, ParametricSystemTools, SemiAlgebraicSetTools, FastArithmeticTools, and AlgebraicGeometryTools, the RegularChains package provides basic commands for computing with polynomials and regular chains. The commands PolynomialRing, DisplayPolynomialRing, MainVariable, Initial, MainDegree, Rank, Tail, and Separant allow the user to manipulate polynomials in the context of regular chains. The commands Equations and Inequations allow the user to inspect a regular chain. The commands RegularGcd, ExtendedRegularGcd, Inverse, IsRegular, RegularizeInitial, NormalForm, SparsePseudoRemainder, and MatrixCombine provide computations modulo regular chains. SuggestVariableOrder attempts to provide an optimal order of variables for speeding up the decomposition of polynomial systems.
The commands Display and Info allow the user to print the different types of objects that the RegularChains package. The former is a raw printer which gives direct access to the object encoding. The latter is a pretty printer.
In addition to RealTriangularize, the commands LazyRealTriangularize and SamplePoints are alternative ways to obtain information on the real solutions of polynomial systems. These two commands solve partially their input system and can return their result much faster than RealTriangularize. In addition, LazyRealTriangularize can be used as an interactive solver, which can be helpful with difficult problems.
Similarly, the command Intersect can be used to solve systems of polynomial equations incrementally (that is, one equation after another) and thus interactively. Therefore, it is also a useful command in complement to Triangularize.
The following is a list of available top-level commands.
To display the help page for a particular RegularChains command, see Getting Help with a Command in a Package.
See the appropriate subpackage help page for a list of commands in the ChainTools, ConstructibleSetTools, FastArithmeticTools, MatrixTools, ParametricSystemTools, SemiAlgebraicSetTools, and AlgebraicGeometryTools subpackages.
The RegularChains example worksheet provides an overview of each of the subpackages.
The MatrixTools subpackage provides commands for solving linear systems of equations modulo the saturated ideal of a regular chain. Among other operations are computations of matrix inverses and lower echelon forms. These commands are considered here in a non-standard context. Indeed, the coefficients of these matrices are polynomials and the computations are performed modulo (the saturated ideal of) a regular chain. Since this latter is not required to be a prime ideal, the commands of this subpackage allow you to do linear algebra computations over non-integral domains.
The ConstructibleSetTools subpackage provides a large set of commands for manipulating constructible sets. Constructible sets are the fundamental objects of Algebraic Geometry, and they play there the role that ideals play in Polynomial Algebra. In broad terms, a constructible set is the solution set of a system of polynomial equations and inequations. Constructible sets appear naturally in many questions, from high-school problems to advanced research topics.
The SemiAlgebraicSetTools subpackage contains a collection of commands for isolating and counting real roots of zero-dimensional semi-algebraic systems or regular chains (that is regular chains with a finite number of complex solutions). It also offers various commands for studying the real solutions of polynomial systems of positive dimension or with parameters. In particular, commands for real root classification, cylindrical algebraic decomposition and partial cylindrical algebraic decomposition sampling are available. Several inspection functions on semi-algebraic systems and their solution sets (namely, semi-algebraic sets) are also provided. They are intended to support the commands RealRootClassification, RealTriangularize and LazyRealTriangularize.
The ParametricSystemTools subpackage provides commands for solving systems of equations that depend on parameters. Given a parametric polynomial system F, this subpackage can be used to answer questions such as: for which values of the parameters does F have solutions? finitely many solutions? N real solutions, for a given N?
The ChainTools subpackage provides advanced operations on regular chains. Most of these commands allow you to inspect, construct and transform regular chains, or to check the properties of a polynomial with respect to a regular chain. Some commands operate transformations on a set of regular chains; they can be used to analyze the results computed by the command Triangularize.
The FastArithmeticTools subpackage contains a collection of commands for computing with regular chains in prime characteristic using asymptotically fast algorithms. Most of the underlying polynomial arithmetic is performed at C level and relies on (multi-dimensional) Fast Fourier Transform (FFT). This imposes some constraints on the characteristic. One of the main purposes of this subpackage is to offer efficient basic routines in order to support the implementation of modular algorithms for computing with regular chains and algebraic numbers.
The AlgebraicGeometryTools subpackage contains a collection of commands for manipulating algebraic curves, surfaces and algebraic sets of higher dimension. The commands currently available mainly focus on computing the limit of a family of sets like limits of a family of secants in the case of tangent cone computation.
Here is a precise definition of a regular chain and its saturated ideal.
First, recall that a non-zero element h of a ring R is called regular if h is not a zero-divisor; that is, for every f of R, if the product f*h is null, then f is null.
Now, let T be a triangular set. We define by induction what it means for T to be a regular chain. Also, we define the saturated ideal of T. If T is empty, then it is a regular chain and its saturated ideal is the trivial ideal (the ideal consisting only of zero). Assume now that T is not empty. Let p be the polynomial of T with greatest main variable and let C be the set of the other polynomials in T. If C is a regular chain with saturated ideal I, and if the initial h of p is regular with respect to I, then T is a regular chain. In addition, the saturated ideal of T is the set of the polynomials g such that there exists a power h^e of h such that h^e * g belongs to the ideal generated by I and p. An important property of a regular chain T is that a polynomial f belongs to the saturated ideal of T if and only if f reduces to zero by pseudo-division with respect to T. The pseudo-division of a polynomial with respect to a regular chain is implemented by the command SparsePseudoRemainder.
It follows from the previous definition that a set consisting of a single polynomial p is a regular chain whose saturated ideal is the ideal generated by the primitive part of p regarded as a univariate polynomial in its main variable.
Let T be a triangular set consisting of two polynomials p and q such that q is univariate in y and p is bivariate in x and y. Let h be the initial of p. Then T is a regular chain if the GCD of q and h is 1. This second example generalizes to regular chains with more than two variables or more than two polynomials. Verifying that a triangular set is a regular chain can be made by means of GCD computations.
These GCD computations take as input two polynomials p1 and p2 with the same main variable v and a regular chain T. Since these GCD computations rely on division (or pseudo-division), the initial of the intermediate remainders (or pseudo-remainders) must be regular modulo the saturated ideal of T. As a consequence, the input polynomials p1 and p2 are required to have regular initials, and the output polynomial, if it has main variable v, also has an initial regular with respect to T. This explains the name of the command RegularGcd. You can check that the input polynomials are valid input by calling IsRegular on their initials. If one of the initials of the input polynomials p1 and p2 is not regular with respect to (the saturated ideal of) T, then you can split T into several regular chains T1,...,Ts such that RegularGcd can be called on p1 and p2 for each of T1,...,Ts. This splitting is obtained by using the RegularizeInitial command on p1 and p2.
Let K be a field and let R a polynomial ring over K obtained by the command PolynomialRing. When R has no parameters, the field K can be Q, the field of rational numbers, or a prime field. When R has parameters, the field K is a field of rational functions. For a set (or a list) F of polynomials of R, the command Triangularize computes the common roots of F in an algebraically closed field L containing K. If K is Q, then one can think of L as the field of the complex numbers. The command Triangularize returns a list of regular chains C1,...,Cs, which is called a triangular decomposition of the common roots of F.
There are two possible relations between the common roots of F and the regular chains C1, ...,Cs, leading to two notions of a triangular decomposition.
We say that C1, ...,Cs is a triangular decomposition of F in the sense of Kalkbrener if the following holds: a point is a root of F if and only if it is a root of one of the saturated ideals of C1,...,Cs.
To introduce the other notion of a triangular decomposition, we need a definition. A point P is a root of a regular chain T if P cancels every polynomial of T but does not cancel any of the initials of the polynomials of T. The commands Equations and Inequations applied to T return the list of its polynomials and the list of their initials, respectively.
We say that C1,...,Cs is a triangular decomposition of F in the sense of Lazard if the following holds: a point is a root of F if and only if it is a root of one of the regular chains C1,...,Cs. A triangular decomposition in the sense of Lazard is in particular a triangular decomposition in the sense of Kalkbrener. But the converse is false.
The command Triangularize is capable of computing both kinds of triangular decompositions. This is achieved by means of options. By default, the sense of Kalkbrener is used. The command Triangularize admits other options that allow the user to control the properties of the computed regular chains. One important property is that of being strongly normalized; see ChainTools for the definition of this notion. Indeed, if T is a strongly normalized regular chain, then you can compute the NormalForm of a polynomial with respect to T.
An irreducible univariate polynomial over K defines both a field extension of K and a regular chain. More generally, let L1 be a direct product of fields, and let p be a univariate polynomial over L1 that generates a radical ideal; then p defines an extension L2 of L1 which is another direct product of fields. It turns out that regular chains are a way to encode extensions of fields or extensions of direct products of fields. This idea is central to the algorithms that the commands IsRegular, Inverse, RegularizeInitial, RegularGcd, and ExtendedRegularGcd implement. The fact that direct products of fields admit zero-divisors is handled by the celebrated D5 principle, which allows us to extend algorithms working fields to direct products of fields.
The theory of regular chains is based on a recursive and univariate vision of polynomials which reduces computations with multivariate polynomials to series of computations with univariate polynomials. The commands MainVariable, Initial, MainDegree, Rank, Tail, and Separant are the basic operations in this recursive and univariate vision of multivariate polynomials.
Presented here is an overview of the RegularChains library by means of a series of examples. The first ones are for non-experts in symbolic computations, whereas the last ones require some familiarity with this area.
Solving polynomial systems by means of regular chains
The first example shows how the RegularChains library can solve systems of algebraic equations symbolically. Start by loading the library.
First, define the ring of the polynomials of the system to be solved. Indeed, most operations of the RegularChains library require such a polynomial ring as a parameter. This is how to specify the variable ordering. See PolynomialRing for more details.
R ≔ PolynomialRing⁡x,y,z
Define a set of polynomials of R.
sys ≔ x2+y+z−1,x+y2+z−1,x+y+z2−1
Ideally, we would like to decompose the solutions of this system into a list of points. In broad terms, this is what the command Triangularize does. However, some of these points are grouped because they share some properties. These groups are described by regular chains.
dec ≔ Triangularize⁡sys,R
Because these points may involve large expressions, you need to ask to see them! The command Equations displays the list of polynomials of a regular chain.
The last three regular chains are very simple: each of them clearly corresponds to a point in the space. Have a closer look at the first one. The polynomial in z has two solutions. To each of them corresponds a point in the space. You can retrieve these five points by using the solve command.
Consider again the regular chain above that corresponds to two points. Since these two points are grouped together, you can check whether each of them is a solution of the input system. This can be achieved by means of the command IsInRadical from the ChainTools subpackage by using the following fact: a regular chain T encodes a subset of the solution set of the input system S if and only if every polynomial of S belongs to the radical of the saturated ideal of T.
Note that Triangularize can also take inequations among its input. Below, impose the condition that x must be different from z.
decn ≔ Triangularize⁡sys,x−z,R;map⁡Equations,decn,R
Observe that two points from the original decomposition have been removed.
If you are solving with the lazard option, then the output is a constructible set, rather than a list of regular chains. Such a distinction matters, if the input system is in positive dimension.
cs ≔ Triangularize⁡op⁡1..2,sys,x−z,R,output=lazard;Info⁡cs,R
decn ≔ Triangularize⁡op⁡1..2,sys,x−z,R;map⁡Equations,decn,R
By default, Triangularize gives generic solutions. With the lazard option, it outputs all solutions, which generally form a constructible set.
Computing inverses modulo a regular chain
The second example illustrates an important feature of the RegularChains library: computations modulo a regular chain. To do so, consider a second system.
sys ≔ x8+y⁢x2+x+z,x2⁢y+3⁢x+2,x2−y⁢x+z
The solution computed by the Triangularize command consists of a single regular chain. In this polynomial ring, the variable ordering makes x>y>z. This means that the x-coordinate of each point must be expressed in terms of y and z, and the y-coordinate as a function of z.
rc ≔ dec1
pz ≔ Polynomial⁡z,rc,R
py ≔ Polynomial⁡y,rc,R
px ≔ Polynomial⁡x,rc,R
The polynomial py gives y as a rational function in z. You may ask if you could express y as a polynomial function in z. In other words, can we replace py by a polynomial with 1 as its Initial? Indeed, the polynomial in z defines a field extension K of the field Q of the rational numbers. In the field K, you can compute the Inverse of the initial of py.
newrc ≔ Under⁡y,rc,R;Equations⁡newrc,R
lcy ≔ Initial⁡py,R;ilcy ≔ Inverse⁡lcy,newrc,R
nilcy ≔ ilcy111;dilcy ≔ ilcy112
The help page for Inverse explains how to read the output of this command. In this example, this output means that the inverse of lcy is a fraction with numerator nilcy and denominator dilcy. To check that ilcy is the inverse of lcy modulo newrc, use the command NormalForm to simplify the product nilcy*lcy. Regular chains have a notion of normal form attached to them, just like Groebner bases.
You obtain dilcy as expected. Now you can make the polynomial py look better by multiplying it by ilcy and removing its content.
newpy ≔ NormalForm⁡nilcy⁢py,newrc,R:cnewpy ≔ content⁡newpy
newpy ≔ newpycnewpy
The same treatment can be applied to the polynomial px.
newrc ≔ Chain⁡newpy,newrc,R;Equations⁡newrc,R
lcx ≔ Initial⁡px,R;ilcx ≔ Inverse⁡lcx,newrc,R
nilcx ≔ ilcx111;dilcx ≔ ilcx112
newpx ≔ NormalForm⁡nilcx⁢px,newrc,R;cnewpx ≔ content⁡newpx
newpx ≔ newpxcnewpx
Then you obtain a new regular newrc chain which encodes the same solution set as rc.
newrc ≔ Chain⁡newpx,newrc,R
polys ≔ Equations⁡rc,R
newpolys ≔ Equations⁡newrc,R
This new regular newrc has an additional property with respect to rc: it is strongly normalized. See IsStronglyNormalized for the definition of strongly normalized. Being strongly normalized is a requirement in order to use the command NormalForm.
You could have obtained this regular chain from the input system by using an option of Triangularize.
decn ≔ Triangularize⁡sys,R,normalized=yes
The Triangularize command does not always return the normalized decomposition so that it can handle the most general cases, including very large examples. Indeed, observe that the first regular chain rc has smaller coefficients than the strongly normalized regular chain newrc.
Automatic case discussion
The next example shows that RegularChains can handle automatic case discussion. Start by trying to answer the following question. Why does the above output of Inverse look complicated? Because RegularChains can handle automatic case discussion! To illustrate this, consider two variables y and z; assume that they are solutions of the regular chain below.
R ≔ PolynomialRing⁡y,z
rc ≔ Empty⁡R
rc ≔ Chain⁡z4+1,y2−z2,rc,R:
Compute the inverse of the following matrix modulo the relations of the regular chain rc.
m ≔ Matrix⁡1,y+z,0,y−z
Clearly, the result depends on whether y and z are equal or not.
mim ≔ MatrixInverse⁡m,rc,R
Check the first result.
m1 ≔ mim111
rc1 ≔ mim112
Consider now the other matrix.
m ≔ Matrix⁡1,y+z,2,y−z
m2 ≔ mim121
rc2 ≔ mim122
Can you get a "generic" answer that would hold both cases? Yes, you can.
clr ≔ MatrixCombine⁡rc1,rc2,R,m1,m2
Recombining the results from a case discussion
The overview of the RegularChains library continues with more advanced examples, extending on the topic of automatic case discussion.
Can you have several cases in the output of MatrixCombine? Yes, this can happen. Reuse the first polynomial system above.
lrc ≔ Triangularize⁡sys,R,normalized=yes;map⁡Equations,lrc,R
Generate four random matrices.
lm ≔ seq⁡Matrix⁡seq⁡seq⁡randpoly⁡x,y,z,degree=1,j=1..2,i=1..2,k=1..4
Now ask for the re-combination of the four cases.
clr ≔ MatrixCombine⁡lrc,R,lm
It turns out that you cannot obtain a unique case. This is surprising, since the saturated ideals of the four regular chains are pairwise relatively prime.
Check why the re-combination into a single regular chain is not possible.
rc1 ≔ clr12
rc2 ≔ clr22
The two ideals generated by rc1 and rc2 are obviously relatively prime (no common roots in z). But if you try to recombine them, you create a polynomial qy in y with a zero-divisor as initial; this is forbidden by the properties of a regular chain. Construct the polynomial qy and check if its initial is a zero-divisor.
Rz ≔ PolynomialRing⁡z
rc ≔ Empty⁡Rz
rc1 ≔ Chain⁡z,rc,Rz
rc2 ≔ Chain⁡z3+z2−3⁢z+1,rc,Rz
m1 ≔ Matrix⁡y2−y
m2 ≔ Matrix⁡2⁢y+z2−1
clr ≔ MatrixCombine⁡rc1,rc2,Rz,m1,m2;m ≔ clr11
rc ≔ clr12;qy ≔ m1,1
Solving systems with an infinite number of solutions
The next example in the overview of RegularChains is a second round for experts. All previous automatic case discussions involve discussions with algebraic numbers only. Can the RegularChains library handle automatic case discussion with parameters? Yes, this is possible. Consider the following system.
R ≔ PolynomialRing⁡x,y,a,b,c,d,g,h
sys ≔ a⁢x+b⁢y−g,c⁢x+d⁢y−h
This new system has a property that the previous examples do not have. Clearly, this new system has an infinite number of solutions, if we view its 8 variables as unknowns. There are two ways of solving such systems. First, by describing its generic solutions, which is done by computing a triangular decomposition in the sense of Kalkbrener.
dec ≔ Triangularize⁡sys,R;map⁡Equations,dec,R
Computing triangular decompositions in the sense of Kalkbrener is the default mode of Triangularize. Observe that the output does not provide explicitly the solutions of the system that cancel the determinant a⁢d−b⁢c. Now compute all the solutions (generic or not); that is, find a triangular decomposition in the sense of Lazard.
dec ≔ Triangularize⁡sys,R,output=lazard
By defining the PolynomialRing correctly, you find that Triangularize can solve polynomial systems with parameters.
R2 ≔ PolynomialRing⁡x,y,a,b,c,d,g,h
dec ≔ Triangularize⁡sys,R2,output=lazard
Similarly, Triangularize can solve polynomial systems in prime characteristic.
R2 ≔ PolynomialRing⁡x,y,a,b,c,d,g,h,3
Controlling the size of the coefficients
Solving systems of equations by means of regular chains can help reduce the size of the coefficients, even when no splitting arises.
In the example below, compare the size of the output of Triangularize with the lexicographical Groebner basis for the same variable ordering. Do not print this Groebner basis since it is quite large; print its size (number of characters) only.
sys ≔ −x5+y5−3⁢y−1,5⁢y4−3,−20⁢x+y−z
dec ≔ Triangularize⁡sys,R;map⁡Equations,dec,R;nops⁡dec
gb ≔ Basis⁡sys,plex⁡x,y,z:length⁡convert⁡gb,string
The commands below illustrate the fact that the RegularChains library provides tools to reduce the size of the coefficients of an output. To see this, use the previous system again, starting from a large output. Indeed, it turns out that for the above system, the lexicographical Groebner basis can be obtained also by using Triangularize with the option normalize=yes. This is because every strongly normalized regular chain T is a lexicographical Groebner basis over the field of the rational functions in the variables that are not algebraic in T. In this example, each variable IsAlgebraic in the output regular chain.
dec ≔ Triangularize⁡sys,R,normalized=yes
Then, the command DahanSchostTransform can be applied to reduce this large regular chain (which is also a lexicographical Groebner basis) into a smaller one.
dst ≔ DahanSchostTransform⁡dec1,R
Check that the two regular chains define the same (saturated) ideal by means of the command EqualSaturatedIdeals.
Splitting for solving
In this library, almost every operation takes a regular chain as a parameter. A regular chain encodes a tower of simple extensions of the underlying field. This tower is a direct product of fields and may contain zero-divisors, so splitting may be needed.
rc ≔ Chain⁡z⁢z−1,rc,R
p1 ≔ z⁢x⁢x+1−z−1⁢x⁢x+2
p2 ≔ z⁢x−1⁢x+1−z−1⁢x+3⁢x+2
As a consequence, every operation (taking a regular chain as a parameter) needs to manage tasks, where a task is [something-to-compute, a-regular-chain].
Manipulating Constructible Sets
This example demonstrates how to manipulate constructible sets, which usually encode the solution set of a polynomial system with both equations and inequations.
R ≔ PolynomialRing⁡x,y,s
Define a polynomial system with equations F and inequations H.
F ≔ s−y+1⁢x,s−x+1⁢y;H ≔ s−1
Use the GeneralConstruct command to create a constructible set cs to encode its solutions.
cs ≔ GeneralConstruct⁡F,H,R
In the RegularChains library, cs is represented by a list of regular systems.
lrs ≔ RepresentingRegularSystems⁡cs,R
Each regular system is a pair consisting of a regular chain and an inequation given by one or more polynomials.
rs ≔ lrs1
rc ≔ RepresentingChain⁡rs,R
h ≔ RepresentingInequations⁡rs,R
The library provides the basic set-theoretic operations on constructible sets, including complementation, union, intersection, difference, inclusion test, and more.
F2 ≔ s−y2+1⁢x,s−x2+1⁢y;H ≔ s−1
cs2 ≔ GeneralConstruct⁡F2,H,R
Besides these, some advanced operations are also provided. See ConstructibleSetTools for details.
Solving Parametric Polynomial Systems
This tour d'horizon concludes with an illustration of how to solve parametric polynomial systems with comprehensive triangular decomposition.
Let U be the last d variables of R, which are regarded as parameters. The output of ComprehensiveTriangularize(sys, d, R) consists of two parts. The first part is a pre-comprehensive triangular decomposition S of sys with respect to the last d variables of R. The second part is a list L of pairs; the first item of each pair is a constructible set and the second item is a list of indices (positive integers) such that the union of these constructible sets forms a partition of the projection of V⁡sys onto the parameter space. Moreover, for each part (or cell) C, the list of positive integers associated with it gives the positions of the regular chains in S satisfying the following property: for each parameter value u in C, the associated regular chains specialized at u form a triangular decomposition of the input system sys specialized at u.
F ≔ s−y+1⁢x,s−x+1⁢y
A comprehensive triangular decomposition of F with respect to parameter s is as follows.