Overview - Maple Help

All Products Maple MapleSim

Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : Overview

Overview of the RegularChains Package

Calling Sequence

Description

List of the RegularChains Package Commands

List of RegularChains Subpackages

Mathematical Definitions

Examples

References

	Calling Sequence
	RegularChains:-command(arguments) command(arguments)

Description

•	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 $S_{1}, ..., S_{n}$ such that a point is a solution of $S$ if and only if it is a solution of one of the systems $S_{1}, ..., S_{n}$ . Each of these simpler systems $S_{1}, ..., S_{n}$ 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, y^{2} + 1]$ is a triangular set, whereas $[x - y + 1, y^{2} - 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, y^{2} - 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.

List of the RegularChains Package Commands

The following is a list of available top-level commands.

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

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.

List of RegularChains 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.

Mathematical Definitions

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 $T_{1}, ..., T_{s}$ 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 $C_{1}, ..., C_{s}$ , 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.

Examples

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.

>	$with (RegularChains) &colon;$ $with (ChainTools) &colon;$ $with (MatrixTools) &colon;$

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])$

$R ≔ polynomial_ring$

(1)

Define a set of polynomials of R.

>	$sys ≔ \{x + y + z^{2} - 1, x + y^{2} + z - 1, x^{2} + y + z - 1\}$

$sys ≔ \{z^{2} + x + y - 1, y^{2} + x + z - 1, x^{2} + y + z - 1\}$

(2)

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)$

$dec ≔ [regular_chain, regular_chain, regular_chain, regular_chain]$

(3)

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.

>	$map (Equations, dec, R)$

$[[x - z, y - z, z^{2} + 2 z - 1], [x, y, z - 1], [x, y - 1, z], [x - 1, y, z]]$

(4)

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.

>	$\{solve (sys)\}$

$\{\{x = 0, y = 0, z = 1\}, \{x = 0, y = 1, z = 0\}, \{x = 1, y = 0, z = 0\}, \{x = RootOf ({_Z}^{2} + 2_Z - 1), y = RootOf ({_Z}^{2} + 2_Z - 1), z = RootOf ({_Z}^{2} + 2_Z - 1)\}\}$

(5)

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.

>	$seq (IsInSaturate (sys [i], dec [1], R), i = 1 .. nops (sys))$

$true, true, true$

(6)

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) &semi;$ $map (Equations, decn, R)$

$decn ≔ [regular_chain, regular_chain]$

$[[x - 1, y, z], [x, y, z - 1]]$

(7)

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) &semi;$ $Info (cs, R)$

$cs ≔ constructible_set$

$[[x + z^{2} + z - 1, y - z], [z^{2} + 2 z - 1]], [[x + z^{2} - z, y + z - 1], [z]]$

(8)

>	$decn ≔ Triangularize ([op (1 .. 2, sys)], [x - z], R) &semi;$ $map (Equations, decn, R)$

$decn ≔ [regular_chain, regular_chain]$

$[[x + z^{2} + z - 1, y - z], [x + z^{2} - z, y + z - 1]]$

(9)

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 ≔ \{x^{2} y + 3 x + 2, x^{8} + y x^{2} + x + z, x^{2} - y x + z\}$

$sys ≔ \{x^{2} y + 3 x + 2, x^{2} - x y + z, x^{8} + x^{2} y + x + z\}$

(10)

>	$dec ≔ Triangularize (sys, R)$

$dec ≔ [regular_chain]$

(11)

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 ≔ dec [1]$

$rc ≔ regular_chain$

(12)

>	$pz ≔ Polynomial (z, rc, R)$

$pz ≔ z^{9} + 22 z^{8} + 208 z^{7} + 1126 z^{6} + 3834 z^{5} + 8136 z^{4} + 9053 z^{3} - 224 z^{2} - 14055 z - 13302$

(13)

>	$py ≔ Polynomial (y, rc, R)$

$py ≔ 4 y z^{6} - 3 z^{7} + 16 y z^{5} + 6 z^{6} + 42 y z^{4} + 426 z^{5} + 742 y z^{3} + 3177 z^{4} + 4056 y z^{2} + 11093 z^{3} + 9416 y z + 21282 z^{2} + 10056 y + 21096 z + 5832$

(14)

>	$px ≔ Polynomial (x, rc, R)$

$px ≔ x y^{2} - y z + 3 x + 2$

(15)

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) &semi;$ $Equations (newrc, R)$

$newrc ≔ regular_chain$

$[z^{9} + 22 z^{8} + 208 z^{7} + 1126 z^{6} + 3834 z^{5} + 8136 z^{4} + 9053 z^{3} - 224 z^{2} - 14055 z - 13302]$

(16)

>	$lcy ≔ Initial (py, R) &semi;$ $ilcy ≔ Inverse (lcy, newrc, R)$

$lcy ≔ 4 z^{6} + 16 z^{5} + 42 z^{4} + 742 z^{3} + 4056 z^{2} + 9416 z + 10056$

$ilcy ≔ [[[43056952878224602831649 z^{8} + 851556715329089933233928 z^{7} + 6829798380079214157184280 z^{6} + 28121353959653668128495638 z^{5} + 58395516864169985401373466 z^{4} + 31177496499998617409832000 z^{3} - 118245600582993390444999143 z^{2} - 157661907907876621441394914 z + 143594593667712002746022313, 100270485333918213150443394312, regular_chain]], []]$

(17)

>	$nilcy ≔ ilcy [1] [1] [1] &semi;$ $dilcy ≔ ilcy [1] [1] [2]$

$nilcy ≔ 43056952878224602831649 z^{8} + 851556715329089933233928 z^{7} + 6829798380079214157184280 z^{6} + 28121353959653668128495638 z^{5} + 58395516864169985401373466 z^{4} + 31177496499998617409832000 z^{3} - 118245600582993390444999143 z^{2} - 157661907907876621441394914 z + 143594593667712002746022313$

$dilcy ≔ 100270485333918213150443394312$

(18)

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.

>	$NormalForm (nilcy lcy, newrc, R)$

$100270485333918213150443394312$

(19)

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) &colon;$ $cnewpy ≔ content (newpy)$

$cnewpy ≔ 8391661701681509748$

(20)

>	$newpy ≔ \frac{newpy}{cnewpy}$

$newpy ≔ 31071832 z^{8} + 559158565 z^{7} + 4309096681 z^{6} + 19396993429 z^{5} + 54553636695 z^{4} + 88747638462 z^{3} + 54918900470 z^{2} + 11948823594 y - 78024336215 z - 156442784340$

(21)

The same treatment can be applied to the polynomial px.

>	$newrc ≔ Chain ([newpy], newrc, R) &semi;$ $Equations (newrc, R)$

$newrc ≔ regular_chain$

$[11948823594 y + 31071832 z^{8} + 559158565 z^{7} + 4309096681 z^{6} + 19396993429 z^{5} + 54553636695 z^{4} + 88747638462 z^{3} + 54918900470 z^{2} - 78024336215 z - 156442784340, z^{9} + 22 z^{8} + 208 z^{7} + 1126 z^{6} + 3834 z^{5} + 8136 z^{4} + 9053 z^{3} - 224 z^{2} - 14055 z - 13302]$

(22)

>	$lcx ≔ Initial (px, R) &semi;$ $ilcx ≔ Inverse (lcx, newrc, R)$

$lcx ≔ y^{2} + 3$

$ilcx ≔ [[[- 336484613006303 z^{8} - 6472881536029244 z^{7} - 52074812760151232 z^{6} - 233680431492813710 z^{5} - 628167256520883558 z^{4} - 914048962864580664 z^{3} - 280077377390474863 z^{2} + 1137261498645304126 z + 1492395674188006257, 822063553694174988, regular_chain]], []]$

(23)

>	$nilcx ≔ ilcx [1] [1] [1] &semi;$ $dilcx ≔ ilcx [1] [1] [2]$

$nilcx ≔ - 336484613006303 z^{8} - 6472881536029244 z^{7} - 52074812760151232 z^{6} - 233680431492813710 z^{5} - 628167256520883558 z^{4} - 914048962864580664 z^{3} - 280077377390474863 z^{2} + 1137261498645304126 z + 1492395674188006257$

$dilcx ≔ 822063553694174988$

(24)

>	$newpx ≔ NormalForm (nilcx px, newrc, R) &semi;$ $cnewpx ≔ content (newpx)$

$newpx ≔ - 1173512875760890 z^{8} - 23382929946795160 z^{7} - 192607789095942472 z^{6} - 872326306307566684 z^{5} - 2350486446974102010 z^{4} - 3377744504245671336 z^{3} - 867887371605727550 z^{2} + 822063553694174988 x + 4280831462806439198 z + 5386815096525691500$

$cnewpx ≔ 68798702$

(25)

>	$newpx ≔ \frac{newpx}{cnewpx}$

$newpx ≔ - 17057195 z^{8} - 339874580 z^{7} - 2799584636 z^{6} - 12679400642 z^{5} - 34164691755 z^{4} - 49096049868 z^{3} - 12614880025 z^{2} + 11948823594 x + 62222561449 z + 78298208250$

(26)

Then you obtain a new regular newrc chain which encodes the same solution set as rc.

>	$newrc ≔ Chain ([newpx], newrc, R)$

$newrc ≔ regular_chain$

(27)

>	$polys ≔ Equations (rc, R)$

$polys ≔ [(y^{2} + 3) x - y z + 2, (4 z^{6} + 16 z^{5} + 42 z^{4} + 742 z^{3} + 4056 z^{2} + 9416 z + 10056) y - 3 z^{7} + 6 z^{6} + 426 z^{5} + 3177 z^{4} + 11093 z^{3} + 21282 z^{2} + 21096 z + 5832, z^{9} + 22 z^{8} + 208 z^{7} + 1126 z^{6} + 3834 z^{5} + 8136 z^{4} + 9053 z^{3} - 224 z^{2} - 14055 z - 13302]$

(28)

>	$newpolys ≔ Equations (newrc, R)$

$newpolys ≔ [11948823594 x - 17057195 z^{8} - 339874580 z^{7} - 2799584636 z^{6} - 12679400642 z^{5} - 34164691755 z^{4} - 49096049868 z^{3} - 12614880025 z^{2} + 62222561449 z + 78298208250, 11948823594 y + 31071832 z^{8} + 559158565 z^{7} + 4309096681 z^{6} + 19396993429 z^{5} + 54553636695 z^{4} + 88747638462 z^{3} + 54918900470 z^{2} - 78024336215 z - 156442784340, z^{9} + 22 z^{8} + 208 z^{7} + 1126 z^{6} + 3834 z^{5} + 8136 z^{4} + 9053 z^{3} - 224 z^{2} - 14055 z - 13302]$

(29)

>	$seq (IsInSaturate (polys [i], newrc, R), i = 1 .. nops (polys))$

$true, true, true$

(30)

>	$seq (IsInSaturate (newpolys [i], rc, R), i = 1 .. nops (newpolys))$

$true, true, true$

(31)

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)$

$decn ≔ [regular_chain]$

(32)

>	$map (Equations, decn, R)$

$[[11948823594 x - 17057195 z^{8} - 339874580 z^{7} - 2799584636 z^{6} - 12679400642 z^{5} - 34164691755 z^{4} - 49096049868 z^{3} - 12614880025 z^{2} + 62222561449 z + 78298208250, 11948823594 y + 31071832 z^{8} + 559158565 z^{7} + 4309096681 z^{6} + 19396993429 z^{5} + 54553636695 z^{4} + 88747638462 z^{3} + 54918900470 z^{2} - 78024336215 z - 156442784340, z^{9} + 22 z^{8} + 208 z^{7} + 1126 z^{6} + 3834 z^{5} + 8136 z^{4} + 9053 z^{3} - 224 z^{2} - 14055 z - 13302]]$

(33)

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])$

$R ≔ polynomial_ring$

(34)

>	$rc ≔ Empty (R)$

$rc ≔ regular_chain$

(35)

>	$rc ≔ Chain ([z^{4} + 1, y^{2} - z^{2}], rc, R) &colon;$

>	$Equations (rc, R)$

$[y^{2} - z^{2}, z^{4} + 1]$

(36)

Compute the inverse of the following matrix modulo the relations of the regular chain rc.

>	$m ≔ Matrix ([[1, y + z], [0, y - z]])$

$m ≔ [\begin{array}{c} 1 & y + z \\ 0 & y - z \end{array}]$

(37)

Clearly, the result depends on whether y and z are equal or not.

>	$mim ≔ MatrixInverse (m, rc, R)$

$mim ≔ [[[[\begin{array}{c} 1 & 0 \\ 0 & \frac{z^{3}}{2} \end{array}], regular_chain]], [[noInv, [\begin{array}{c} 1 & y + z \\ 0 & y - z \end{array}], regular_chain]]]$

(38)

Check the first result.

>	$m1 ≔ mim [1] [1] [1]$

$m1 ≔ [\begin{array}{c} 1 & 0 \\ 0 & \frac{z^{3}}{2} \end{array}]$

(39)

>	$rc1 ≔ mim [1] [1] [2]$

$rc1 ≔ regular_chain$

(40)

>	$Equations (rc1, R)$

$[y + z, z^{4} + 1]$

(41)

>	$MatrixMultiply (m1, m, rc1, R)$

$[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}]$

(42)

Consider now the other matrix.

>	$m ≔ Matrix ([[1, y + z], [2, y - z]])$

$m ≔ [\begin{array}{c} 1 & y + z \\ 2 & y - z \end{array}]$

(43)

>	$mim ≔ MatrixInverse (m, rc, R)$

$mim ≔ [[[[\begin{array}{c} 1 & 0 \\ - z^{3} & \frac{z^{3}}{2} \end{array}], regular_chain], [[\begin{array}{c} 0 & \frac{1}{2} \\ - \frac{z^{3}}{2} & \frac{z^{3}}{4} \end{array}], regular_chain]], []]$

(44)

Double check.

>	$m1 ≔ mim [1] [1] [1]$

$m1 ≔ [\begin{array}{c} 1 & 0 \\ - z^{3} & \frac{z^{3}}{2} \end{array}]$

(45)

>	$rc1 ≔ mim [1] [1] [2]$

$rc1 ≔ regular_chain$

(46)

>	$m2 ≔ mim [1] [2] [1]$

$m2 ≔ [\begin{array}{c} 0 & \frac{1}{2} \\ - \frac{z^{3}}{2} & \frac{z^{3}}{4} \end{array}]$

(47)

>	$rc2 ≔ mim [1] [2] [2]$

$rc2 ≔ regular_chain$

(48)

>	$MatrixMultiply (m2, m, rc2, R)$

$[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}]$

(49)

>	$MatrixMultiply (m2, m, rc2, R)$

$[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}]$

(50)

Can you get a "generic" answer that would hold both cases? Yes, you can.

>	$clr ≔ MatrixCombine ([rc1, rc2], R, [m1, m2])$

$clr ≔ [[[\begin{array}{c} \frac{y z^{3}}{2} + \frac{1}{2} & - \frac{y z^{3}}{4} + \frac{1}{4} \\ \frac{1}{4} y z^{2} - \frac{3}{4} z^{3} & - \frac{1}{8} y z^{2} + \frac{3}{8} z^{3} \end{array}], regular_chain]]$

(51)

Check.

>	$MatrixMultiply (clr [1] [1], m, clr [1] [2], R)$

$[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}]$

(52)

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.

>	$R ≔ PolynomialRing ([x, y, z])$

$R ≔ polynomial_ring$

(53)

>	$sys ≔ \{x + y + z^{2} - 1, x + y^{2} + z - 1, x^{2} + y + z - 1\}$

$sys ≔ \{z^{2} + x + y - 1, y^{2} + x + z - 1, x^{2} + y + z - 1\}$

(54)

>	$lrc ≔ Triangularize (sys, R, normalized = yes) &semi;$ $map (Equations, lrc, R)$

$lrc ≔ [regular_chain, regular_chain, regular_chain, regular_chain]$

$[[x - z, y - z, z^{2} + 2 z - 1], [x, y, z - 1], [x, y - 1, z], [x - 1, y, z]]$

(55)

Generate four random matrices.

>	$randomize (4869257127) &colon;$

>	$lm ≔ [seq (Matrix ([seq ([seq (randpoly ([x, y, z], degree = 1), j = 1 .. 2)], i = 1 .. 2)]), k = 1 .. 4)]$

$lm ≔ [[\begin{array}{c} 40 x + 17 y + 49 z + 75 & - 9 x + 71 y + 22 z + 68 \\ 79 x + 26 y - 35 z + 21 & - 48 x - 80 y - 32 z - 85 \end{array}], [\begin{array}{c} - 78 x - 35 y + 50 z - 26 & 32 x + 47 y + 32 z + 69 \\ 34 x + 58 y - 8 z - 63 & 98 x + 84 y - 71 z + 38 \end{array}], [\begin{array}{c} 49 x - 56 y + 36 z + 4 & - 98 x + 46 y - 43 z + 79 \\ 80 x - y + 49 z - 14 & - 52 x + 5 y - 46 z + 1 \end{array}], [\begin{array}{c} 29 x + 65 y + 7 z - 22 & 29 x - 12 y - 31 z + 25 \\ 50 x - 5 y + 28 z + 3 & - 34 x + 82 y - 96 z - 48 \end{array}]]$

(56)

Now ask for the re-combination of the four cases.

>	$clr ≔ MatrixCombine (lrc, R, lm)$

$clr ≔ [[[\begin{array}{c} - 59 y + 7 & 71 y + 54 \\ - 68 y + 53 & 88 y - 82 \end{array}], regular_chain], [[\begin{array}{c} - \frac{157}{2} z^{2} - 51 z + \frac{307}{2} & - \frac{51}{2} z^{2} + 33 z + \frac{187}{2} \\ - 81 z^{2} - 92 z + 102 & 106 z^{2} + 52 z - 191 \end{array}], regular_chain]]$

(57)

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 ≔ clr [1] [2]$

$rc1 ≔ regular_chain$

(58)

>	$Equations (rc1, R)$

$[x + y - 1, y^{2} - y, z]$

(59)

>	$rc2 ≔ clr [2] [2]$

$rc2 ≔ regular_chain$

(60)

>	$Equations (rc2, R)$

$[2 x + z^{2} - 1, 2 y + z^{2} - 1, z^{3} + z^{2} - 3 z + 1]$

(61)

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])$

$Rz ≔ polynomial_ring$

(62)

>	$rc ≔ Empty (Rz)$

$rc ≔ regular_chain$

(63)

>	$rc1 ≔ Chain ([z], rc, Rz)$

$rc1 ≔ regular_chain$

(64)

>	$rc2 ≔ Chain ([z^{3} + z^{2} - 3 z + 1], rc, Rz)$

$rc2 ≔ regular_chain$

(65)

>	$m1 ≔ Matrix ([[y^{2} - y]])$

$m1 ≔ [\begin{array}{c} y^{2} - y \end{array}]$

(66)

>	$m2 ≔ Matrix ([[2 y + z^{2} - 1]])$

$m2 ≔ [\begin{array}{c} 2 y + z^{2} - 1 \end{array}]$

(67)

>	$clr ≔ MatrixCombine ([rc1, rc2], Rz, [m1, m2]) &semi;$ $m ≔ clr [1] [1]$

$clr ≔ [[[\begin{array}{c} y^{2} z^{3} + y^{2} z^{2} - 3 y z^{3} - 3 y^{2} z - 3 y z^{2} + z^{3} + y^{2} + 9 y z + 2 z^{2} - y - 3 z \end{array}], regular_chain]]$

$m ≔ [\begin{array}{c} y^{2} z^{3} + y^{2} z^{2} - 3 y z^{3} - 3 y^{2} z - 3 y z^{2} + z^{3} + y^{2} + 9 y z + 2 z^{2} - y - 3 z \end{array}]$

(68)

>	$rc ≔ clr [1] [2] &semi;$ $qy ≔ m [1, 1]$

$rc ≔ regular_chain$

$qy ≔ y^{2} z^{3} + y^{2} z^{2} - 3 y z^{3} - 3 y^{2} z - 3 y z^{2} + z^{3} + y^{2} + 9 y z + 2 z^{2} - y - 3 z$

(69)

>	$Inverse (Initial (qy, R), rc, Rz)$

$[[[1, 1, regular_chain]], [regular_chain, regular_chain]]$

(70)

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])$

$R ≔ polynomial_ring$

(71)

>	$sys ≔ \{a x + b y - g, c x + d y - h\}$

$sys ≔ \{a x + b y - g, c x + d y - h\}$

(72)

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) &semi;$ $map (Equations, dec, R)$

$dec ≔ [regular_chain]$

$[[c x + y d - h, (a d - b c) y - a h + c g]]$

(73)

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)$

$dec ≔ [regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain]$

(74)

>	$map (Equations, dec, R) &semi;$ $map (Inequations, dec, R)$

$[[c x + d y - h, (d a - b c) y - h a + c g], [c x + d y - h, d a - b c, h b - d g], [a x + b y - g, d y - h, c], [d y - h, a, h b - d g, c], [c x - h, h a - c g, b, d], [a x + b y - g, c, d, h], [c x + d y, d a - b c, g, h], [b y - g, a, c, d, h], [y, a, c, g, h], [x, b, d, g, h], [a, b, c, d, g, h]]$

$[\{c, d a - b c\}, \{c, d, h\}, \{a, d\}, \{d, h\}, \{c, h\}, \{a\}, \{c, d\}, \{b\}, \emptyset, \emptyset, \emptyset]$

(75)

>	$[seq ([eq = Equations (dec [i], R), ineq = Inequations (dec [i], R)], i = 1 .. nops (dec))]$

$[[eq = [c x + d y - h, (d a - b c) y - h a + c g], ineq = \{c, d a - b c\}], [eq = [c x + d y - h, d a - b c, h b - d g], ineq = \{c, d, h\}], [eq = [a x + b y - g, d y - h, c], ineq = \{a, d\}], [eq = [d y - h, a, h b - d g, c], ineq = \{d, h\}], [eq = [c x - h, h a - c g, b, d], ineq = \{c, h\}], [eq = [a x + b y - g, c, d, h], ineq = \{a\}], [eq = [c x + d y, d a - b c, g, h], ineq = \{c, d\}], [eq = [b y - g, a, c, d, h], ineq = \{b\}], [eq = [y, a, c, g, h], ineq = \emptyset], [eq = [x, b, d, g, h], ineq = \emptyset], [eq = [a, b, c, d, g, h], ineq = \emptyset]]$

(76)

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\})$

$R2 ≔ polynomial_ring$

(77)

>	$dec ≔ Triangularize (sys, R2, output = lazard)$

$dec ≔ [regular_chain, regular_chain, regular_chain, regular_chain, regular_chain]$

(78)

>	$[seq ([eq = Equations (dec [i], R2), ineq = Inequations (dec [i], R2)], i = 1 .. nops (dec))]$

$[[eq = [c x + d y - h, (d a - b c) y - h a + c g], ineq = \{c, d a - b c\}], [eq = [c x + d y - h, d a - b c, h b - d g], ineq = \{c, d\}], [eq = [a x + y b - g, d y - h, c], ineq = \{a, d\}], [eq = [d y - h, a, h b - d g, c], ineq = \{d\}], [eq = [c x - h, h a - c g, b, d], ineq = \{c\}]]$

(79)

Similarly, Triangularize can solve polynomial systems in prime characteristic.

>	$R2 ≔ PolynomialRing ([x, y, a, b, c, d], \{g, h\}, 3)$

$R2 ≔ polynomial_ring$

(80)

>	$dec ≔ Triangularize (sys, R2, output = lazard)$

$dec ≔ [regular_chain, regular_chain, regular_chain, regular_chain, regular_chain]$

(81)

>	$[seq ([eq = Equations (dec [i], R2), ineq = Inequations (dec [i], R2)], i = 1 .. nops (dec))]$

$[[eq = [c x + d y + 2 h, (d a + 2 b c) y + 2 h a + c g], ineq = \{c, d a + 2 b c\}], [eq = [c x + d y + 2 h, d a + 2 b c, h b + 2 d g], ineq = \{c, d\}], [eq = [a x + y b + 2 g, d y + 2 h, c], ineq = \{a, d\}], [eq = [d y + 2 h, a, h b + 2 d g, c], ineq = \{d\}], [eq = [c x + 2 h, h a + 2 c g, b, d], ineq = \{c\}]]$

(82)

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.

>	$R ≔ PolynomialRing ([x, y, z])$

$R ≔ polynomial_ring$

(83)

>	$sys ≔ \{5 y^{4} - 3, - 20 x + y - z, - x^{5} + y^{5} - 3 y - 1\}$

$sys ≔ \{- 20 x + y - z, 5 y^{4} - 3, - x^{5} + y^{5} - 3 y - 1\}$

(84)

>	$dec ≔ Triangularize (sys, R) &semi;$ $map (Equations, dec, R) &semi;$ $nops (dec)$

$dec ≔ [regular_chain]$

$[[20 x - y + z, (4375 z^{12} + 52800011625 z^{8} + 32000000000 z^{7} + 110591902080002925 z^{4} + 61439980800000000 z^{3} + 12800000000000000 z^{2} + 56623117271041036800027) y - 1875 z^{13} - 9600010125 z^{9} + 2000000000 z^{8} - 7372714752004545 z^{5} + 30720002400000000 z^{4} + 12800000000000000 z^{3} - 22118403456000135 z + 23592963686400144000000, 3125 z^{20} - 9375 z^{16} - 40000000000 z^{15} - 2015999988750 z^{12} - 1560000000000 z^{11} + 192000000000000000 z^{10} - 12165125356800006750 z^{8} - 14745602232000000000 z^{7} - 6528000000000000000 z^{6} - 409600000000000000000000 z^{5} - 16986908639233347839997975 z^{4} - 14155767152640302400000000 z^{3} - 5898238732800000000000000 z^{2} - 1228800000000000000000000 z - 6195303619231982878732441600243]]$

$1$

(85)

>	$length (convert (map (Equations, dec, R), string))$

$654$

(86)

>	$with (Groebner) &colon;$

>	$gb ≔ Basis (sys, plex (x, y, z)) &colon;$ $length (convert (gb, string))$

$8674$

(87)

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)$

$dec ≔ [regular_chain]$

(88)

>	$length (convert (map (Equations, dec, R), string))$

$8674$

(89)

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 (dec [1], R)$

$dst ≔ regular_chain$

(90)

>	$length (convert (Equations (dst, R), string))$

$1533$

(91)

Check that the two regular chains define the same (saturated) ideal by means of the command EqualSaturatedIdeals.

>	$EqualSaturatedIdeals (dec [1], dst, R)$

$true$

(92)

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.

>	$R ≔ PolynomialRing ([x, y, z])$

$R ≔ polynomial_ring$

(93)

>	$rc ≔ Empty (R)$

$rc ≔ regular_chain$

(94)

>	$rc ≔ Chain ([z (z - 1)], rc, R)$

$rc ≔ regular_chain$

(95)

>	$p1 ≔ z x (x + 1) - (z - 1) x (x + 2)$

$p1 ≔ z x (x + 1) - (z - 1) x (x + 2)$

(96)

>	$p2 ≔ z (x - 1) (x + 1) - (z - 1) (x + 3) (x + 2)$

$p2 ≔ z (x - 1) (x + 1) - (z - 1) (x + 3) (x + 2)$

(97)

>	$expand (p1)$

$x^{2} - x z + 2 x$

(98)

>	$expand (p2)$

$x^{2} - 5 x z + 5 x - 7 z + 6$

(99)

>	$RegularGcd (p1, p2, x, rc, R)$

$[[(- 4 z + 3) x - 7 z + 6, regular_chain]]$

(100)

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.

>	$with (ConstructibleSetTools) &colon;$

>	$R ≔ PolynomialRing ([x, y, s])$

$R ≔ polynomial_ring$

(101)

Define a polynomial system with equations F and inequations H.

>	$F ≔ [s - (y + 1) x, s - (x + 1) y] &semi;$ $H ≔ [s - 1]$

$F ≔ [s - (y + 1) x, s - (x + 1) y]$

$H ≔ [s - 1]$

(102)

Use the GeneralConstruct command to create a constructible set cs to encode its solutions.

>	$cs ≔ GeneralConstruct (F, H, R)$

$cs ≔ constructible_set$

(103)

In the RegularChains library, cs is represented by a list of regular systems.

>	$lrs ≔ RepresentingRegularSystems (cs, R)$

$lrs ≔ [regular_system, regular_system]$

(104)

Each regular system is a pair consisting of a regular chain and an inequation given by one or more polynomials.

>	$rs ≔ lrs [1]$

$rs ≔ regular_system$

(105)

>	$rc ≔ RepresentingChain (rs, R)$

$rc ≔ regular_chain$

(106)

>	$h ≔ RepresentingInequations (rs, R)$

$h ≔ [s - 1]$

(107)

The library provides the basic set-theoretic operations on constructible sets, including complementation, union, intersection, difference, inclusion test, and more.

>	$F2 ≔ [s - (y^{2} + 1) x, s - (x^{2} + 1) y] &semi;$ $H ≔ [s - 1]$

$F2 ≔ [s - (y^{2} + 1) x, s - (x^{2} + 1) y]$

$H ≔ [s - 1]$

(108)

>	$cs2 ≔ GeneralConstruct (F2, H, R)$

$cs2 ≔ constructible_set$

(109)

>	$Complement (cs, R)$

$constructible_set$

(110)

>	$Union (cs, cs2, R)$

$constructible_set$

(111)

>	$Intersection (cs, cs2, R)$

$constructible_set$

(112)

>	$Difference (cs, cs2, R)$

$constructible_set$

(113)

>	$IsContained (cs, cs2, R)$

$false$

(114)

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$ .

>	$R ≔ PolynomialRing ([x, y, s])$

$R ≔ polynomial_ring$

(115)

>	$F ≔ [s - (y + 1) x, s - (x + 1) y]$

$F ≔ [s - (y + 1) x, s - (x + 1) y]$

(116)

A comprehensive triangular decomposition of F with respect to parameter $s$ is as follows.

>	$with (ParametricSystemTools) &colon;$

>	$pctd, cells ≔ ComprehensiveTriangularize (F, 1, R)$

$pctd, cells ≔ [regular_chain, regular_chain, regular_chain], [[constructible_set, [3, 2]], [constructible_set, [1]]]$

(117)

The first part of the output is the pre-comprehensive triangular decomposition of F, which consists of three regular chains.

>	$map (Info, pctd, R)$

$[[(y + 1) x - s, y^{2} + y - s], [x + 1, y + 1, s], [x, y, s]]$

(118)

The projection of $V (F)$ onto the parameter space has been partitioned into two disjoint constructible sets.

>	$with (ConstructibleSetTools) &colon;$

>	$cs1 ≔ cells [1] [1] &semi;$ $Info (cs1, R)$

$cs1 ≔ constructible_set$

$[[s], [1]]$

(119)

>	$cs2 ≔ cells [2] [1] &semi;$ $Info (cs2, R)$

$cs2 ≔ constructible_set$

$[[], [s]]$

(120)

Thus, when the parameter value $s$ is in cs1, the last two regular chains (after specialization) form a triangular decomposition of $F (s)$ . Otherwise, $s$ is in cs2, and the first regular chain forms a triangular decomposition of $F (s)$ .

References

The theory of regular chains was introduced independently by M. Kalkbrener in his PhD Thesis: "Three contributions to elimination theory." and by L. Yang and J. Zhang in the paper "Searching dependency between algebraic equations: an algorithm." Regular chains and their related concepts (triangular sets and saturated ideals) are discussed in the paper "On the theories of triangular sets," co-authored by P. Aubry, D. Lazard, and M. Moreno Maza. The paper "When does T equal Sat(T)?" by F. Lemaire, M. Moreno Maza, W. Pan and Y. Xie, contains a more up-to-date summary of these ideas.

The algorithms implemented in the RegularChains package are mainly taken from the paper "On Triangular Decompositions of Algebraic Varieties" by M. Moreno Maza, available at the author's web page. The other algorithms are taken from the papers "Lifting techniques for triangular decompositions" (X. Dahan, M. Moreno Maza, E. Schost, W. Wu, and Y. Xie), "Change of ordering for regular chains in positive dimension" (X. Dahan, X. Jin, M. Moreno Maza, and E. Schost, 2007), "Comprehensive Triangular Decomposition" (C. Chen, F. Lemaire, O. Golubitsky, M. Moreno Maza, and W. Pan, 2007), "Efficient Computations of Irredundant Triangular Decompositions with the RegularChains Library" (C. Chen, F. Lemaire, M. Moreno Maza, W. Pan, and Y. Xie, 2007), "Computations modulo regular chains" (X. Li, M. Moreno Maza, W. Pan, 2009), "Cylindrical Algebraic Decomposition via Triangular Decomposition" (C. Chen, M. Moreno Maza, B. Xia and L. Yang, 2009) and "Triangular Decomposition of Semi-algebraic Systems" (C. Chen, J.H. Davenport, J.P. May, M. Moreno Maza, B. Xia and R. Xiao, 2010)

The RegularChains library was originally designed and integrated into Maple by F. Lemaire (Univ. of Lille, France) M. Moreno Maza (Univ. of Western Ontario, Canada) and Y. Xie (Univ. of Western Ontario, Canada). Today, the design, implementation, and maintenance is mainly the work of C. Chen, M. Moreno Maza and R. Xiao (all of them from the Univ. of Western Ontario, Canada). Large contributions have been made by X. Jin, L. Li, X. Li, E. Schost, W. Pan, and W. Wu (all of them from the Univ. of Western Ontario, Canada) and by B. Xia (Peking University, China). X. Dahan (Kyushu University, Japan) and H. Ding, N. Islam, Y. Li, A. Shakoori, W. Zhou, and J. Zhao (Univ. of Western Ontario, Canada) have also participated in the development of the RegularChains package.

Aubry, P.; Lazard, D. and Moreno Maza, M. "On the theories of triangular sets." J. Symb. Comp., Vol. 28 (1999): 105-124.

F. Boulier, C. Chen, F. Lemaire, M. Moreno Maza "Real root isolation of regular chains." ASCM'09, Math-for-Industry, Lecture Note Series Vol. 22 (2009):15-29.

Boulier, F. and Lemaire, F. "Computing canonical representatives of regular differential ideals." In Proc. ISSAC 2000. St Andrews, Scotland, 2000.

Boulier, F.; Lemaire, F. and Moreno Maza, M. "Well known theorems on triangular systems and the D5 Principle." In Proceedings of Transgressive Computing 2006. Edited by J.-G. Dumas. Spain: University of Granada, 2006.

Chen. C.; Lemaire, F.; Golubitsky, O.; Moreno Maza, M. and Pan, W. "Comprehensive Triangular Decomposition." Proceedings of CASC 2007, Lecture Notes in Computer Science, Vol. 4770. Springer, 2007.

Chen, C.; Lemaire, F.; Moreno Maza, M.; Pan, W. and Xie, Y. "Efficient Computations of Irredundant Triangular Decompositions with the RegularChains Library." Proceedings of CASA 2007, Lecture Notes in Computer Science, Vol. 4488. Springer, 2007.

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

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

Dahan, X.; Moreno Maza, M.; Schost, E. and Xie, Y. "On the complexity of the D5 Principle." In Proceedings of Transgressive Computing 2006, Edited by J.-G. Dumas. Spain: University of Granada, 2006.

Dahan, X.; Jin, X.; Moreno Maza, M. and Schost, E. "Change of ordering for regular chains in positive dimension." J. of Theoretical Computer Science, Vol. 392 (2008): 3765.

Della Dora, J.; Discrescenzo, C. and Duval, D. "About a new method for computing in algebraic number fields." In Proc. EUROCAL 85 Vol. 2. 1985.

Kalkbrener, M. "A generalized Euclidean algorithm for computing triangular representations of algebraic varieties." J. Symb. Comp., Vol. 15 (1993): 143-167.

Kalkbrener, M. "Three contributions to elimination theory." PhD Thesis, University of Linz, Austria, 1991.

Lazard, D. "Solving zero-dimensional algebraic systems." J. Symb. Comp., Vol. 13 (1992): 117-133.

Lemaire, F.; Moreno Maza, M. and Xie, Y. "The RegularChains library." In Proceedings of Maple Conference' 05, pp. 355-368. Edited by I. Kotsireas. 2005.

Lemaire, F.; Moreno Maza, M.; Pan, W. and Xie, Y. "When does T equal Sat(T)?" In Proc. ISSAC 2008. Linz, Austria, 2008.

Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties." MEGA-2000 conference. Bath, UK, England.

Moreno Maza, M. and Rioboo, R. "Polynomial GCD computations over towers of algebraic extensions" In proc. of AAECC-11, Lecture Notes in Comput. Sci, Vol. 948. Springer, 1995.

Moreno Maza, M. and Xie, Y. "Component-level parallelization of triangular decompositions." In Proceedings of Parallel Symbolic Computation'07, pp. 69-77, ACM Press, NY, USA, 2007.

Schost, E. "Complexity results for triangular sets." J. Symb. Comp., Vol. 36 No. 3-4 (2003): 555-594.

Wang, D. M. "An elimination method for polynomial systems." J. Symb. Comp., Vol. 16 (1993): 83-114.

Wang, D. M. Elimination Methods. Wein, New York: Springer, 2000.

Wu, W. T. "Basic principles of mechanical theorem proving in elementary." J. Sys. Sci. and Math. Scis, Vol. 4 (1984): 207-235.

Yang, L. and Zhang, J. "Searching dependency between algebraic equations: an algorithm." Artificial intelligence in mathematics. Oxford University Press, 1994.

Download Help Document

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim