|
RegularChains[Triangularize] - compute the triangular decomposition of a polynomial system
|
|
Calling Sequence
|
|
Triangularize(F, R)
Triangularize(F, H, R)
Triangularize(F, rc, R)
Triangularize(F, H, rc, R)
Triangularize(F, R, 'normalized'='yes')
Triangularize(F, R, 'radical'='yes')
Triangularize(F, R, 'output'='lazard')
Triangularize(F, R, 'probability'='prob')
|
|
|
Parameters
|
|
|
F
|
-
|
list or set of equations
|
|
R
|
-
|
polynomial ring
|
|
H
|
-
|
(optional) list or set of inequations
|
|
rc
|
-
|
(optional) regular chain
|
|
'normalized'='yes'
|
-
|
(optional) boolean flag
|
|
'radical'='yes'
|
-
|
(optional) boolean flag
|
|
'output'='lazard'
|
-
|
(optional) boolean flag
|
|
'probability'='prob'
|
-
|
(optional) numerical value
|
|
|
|
|
|
Description
|
|
|
•
|
The command Triangularize(F,H,rc,R) returns a triangular decomposition of the set of the zeros of F that are zeros of rc but not zeros of H.
|
|
•
|
If H is not specified, it is set to ![[1]](/support/helpjp/helpview.aspx?si=4974/file02701/math178.png) .
|
|
•
|
If rc is not specified, it is set to the empty regular chain.
|
|
•
|
If H=[1] and rc is empty, this command returns a triangular decomposition of the set of the zeros of F.
|
|
•
|
Each element of this triangular decomposition is a regular chain.
|
|
•
|
The concepts of a regular chain and a triangular decomposition are defined in the page RegularChains.
|
|
•
|
The algorithm for the command Triangularize is described in the paper "On Triangular Decompositions of Algebraic Varieties" by Marc Moreno Maza, available on the author's web page.
|
|
•
|
This command is part of the RegularChains package, so it can be used in the form Triangularize(..) only after executing the command with(RegularChains). However, it can always be accessed through the long form of the command by using RegularChains[Triangularize](..).
|
|
|
|
Options
|
|
|
•
|
If 'normalized'='yes', each of the returned regular chains is normalized. If 'normalized'='strongly', each regular chain is strongly normalized. By default, each regular chain may not be normalized.
|
|
•
|
If 'radical'='yes', the saturated ideal of each regular chain is radical. By default, the saturated ideal of each regular chain may not be radical.
|
|
|
This option is currently only supported if the characteristic of the polynomial ring R is zero.
|
|
•
|
If 'output'='lazard', the decomposition is the sense of Lazard; otherwise, it is made in the sense of Kalkbrener. The latter is weaker but less expensive to compute. When F has only a finite number of solutions, both senses coincide.
|
|
|
As mentioned above, if this option is specified and if inequations (the input polynomial list H) are present, then the output is a constructible set. See the commands of the subpackage ConstructibleSetTools for operations on constructible sets.
|
|
|
If a non-empty regular chain rc is provided, then the decomposition is the sense of Lazard, whether 'output'='lazard' is specified or not.
|
|
•
|
If 'probability'='prob', the probabilistic algorithm of Dahan, Moreno Maza, Schost, Wu, and Xie (ISSAC 2005) is used. This algorithm applies only to square systems in characteristic zero. In this implementation, it will fail if two primes such that the system modulo those primes is radical cannot be found after ten tries. This option is not compatible with any other options.
|
|
•
|
The options 'output'='lazard' and 'normalized'='yes' cannot be mixed in the current implementation of this command. (This limitation will be solved in the next version of the RegularChains library).
|
|
•
|
The commands BivariateModularTriangularize and ChangeOfOrder implement algorithms for computing triangular decompositions under particular circumstances. When they apply, they are likely to outperform Triangularize.
|
|
|
|
Examples
|
|
|
>
|
|
Define a ring of polynomials.
|
>
|
![R := PolynomialRing([z, y, x])](/support/helpjp/helpview.aspx?si=4974/file02701/math287.png)
|
|
| (1) |
Define a set of polynomials of R. Each of them will be viewed as an equality to 0.
|
>
|
![sys := [x^2+y+z-1, x+y^2+z-1, x+y+z^2-1]](/support/helpjp/helpview.aspx?si=4974/file02701/math298.png)
|
|
![sys := [x^2+y+z-1, x+y^2+z-1, x+y+z^2-1]](/support/helpjp/helpview.aspx?si=4974/file02701/math301.png)
| (2) |
Ideally, you would like to decompose the set of the common solutions of sys into a list of points. The Triangularize command does this by using symbolic expressions. Sometimes several points are grouped together in a generic one, as in this example. These groups of points are called regular chains, and they are grouped together because they share some mathematical properties.
|
>
|
|
|
![dec := [regular_chain, regular_chain, regular_chain, regular_chain]](/support/helpjp/helpview.aspx?si=4974/file02701/math314.png)
| (3) |
Since regular chains may contain large expressions, their output form is just a word. To view their members, use the Equations command.
|
>
|
|
|
![[[z-x, y-x, x^2+2*x-1], [z, y, x-1], [z, y-1, x], [z-1, y, x]]](/support/helpjp/helpview.aspx?si=4974/file02701/math326.png)
| (4) |
The first three regular chains are very simple: each of them clearly corresponds to a single point. The fourth regular chain corresponds to two points, because its univariate polynomial in  has two roots. Consider now another polynomial ring and another polynomial system.
|
>
|
![R := PolynomialRing([x, y, a, b, c, d, g, h])](/support/helpjp/helpview.aspx?si=4974/file02701/math334.png)
|
|
| (5) |
|
>
|
![sys := [a*x+b*y-g, c*x+d*y-h]](/support/helpjp/helpview.aspx?si=4974/file02701/math341.png)
|
|
![sys := [a*x+b*y-g, c*x+d*y-h]](/support/helpjp/helpview.aspx?si=4974/file02701/math344.png)
| (6) |
In the polynomial ring, the ordering on the variables is such that  . Solving  with this ordering implies that you want to express  and  as functions of the other variables. Hence you can view the system  as a parametric linear system with two equations and two unknowns,  and  . Applying RegularChains[Triangularize] displays the generic solution, which is similar to the solution given by Groebner[Solve].
|
>
|
 
|
|
![[[c*x+y*d-h, (a*d-b*c)*y-a*h+c*g]]](/support/helpjp/helpview.aspx?si=4974/file02701/math375.png)
| (7) |
|
>
|
|
|
![{[[-x*a-y*b+g, -c*x-y*d+h], plex(h, g, d, c, b, a, y, x), {}]}](/support/helpjp/helpview.aspx?si=4974/file02701/math382.png)
| (8) |
This generic solution assumes that the determinant of the system is not zero. With the option output=lazard, Triangularize gives all of the solutions, including those that cancel the determinant of the input system.
|
>
|
|
|
![decl := [regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain, regular_chain]](/support/helpjp/helpview.aspx?si=4974/file02701/math395.png)
| (9) |
|
>
|
|
|
![[[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]]](/support/helpjp/helpview.aspx?si=4974/file02701/math402.png)
| (10) |
|
>
|
|
|
| (11) |
You already know that each regular chain is associated with a set of equations. It is also associated with a set of inequations.
|
| (12) |
The inequations of a regular chain  are the set of the initials of the polynomials of  . In the first regular chain above, the inequations are  and  . Hence, for this regular chain, none of these two polynomials should vanish. The solutions of  that cancel either  or the determinant  are given by the other regular chains of  . Below, for each regular chain of  , we print its list of equations together with its set of inequations.
|
>
|
![[seq([eq = Equations(decl[i], R), ineq = Inequations(decl[i], R)], i = 1 .. nops(decl))]](/support/helpjp/helpview.aspx?si=4974/file02701/math450.png)
|
|
![[[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 = {}], [eq = [x, b, d, g, h], ineq = {}], [eq = [a, b, c, d, g, h], ineq = {}]]](/support/helpjp/helpview.aspx?si=4974/file02701/math453.png)
| (13) |
Assume now that you want to see  and  as transcendental quantities; that is, quantities that cannot satisfy any polynomial equations. Then you need to redefine the polynomial ring as follows.
|
>
|
![R2 := PolynomialRing([x, y, a, b, c, d], {g, h})](/support/helpjp/helpview.aspx?si=4974/file02701/math463.png)
|
|
| (14) |
|
>
|
|
|
![dec2 := [regular_chain, regular_chain, regular_chain, regular_chain, regular_chain]](/support/helpjp/helpview.aspx?si=4974/file02701/math473.png)
| (15) |
|
>
|
![[seq([eq = Equations(dec2[i], R2), ineq = Inequations(dec2[i], R2)], i = 1 .. nops(dec2))]](/support/helpjp/helpview.aspx?si=4974/file02701/math477.png)
|
|
![[[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}]]](/support/helpjp/helpview.aspx?si=4974/file02701/math480.png)
| (16) |
|
>
|
|
|
| (17) |
Now, you can obtain five regular chains, none of them imposing a condition on  or  . The following example uses the option probability, by which a triangular decomposition is done by using a modular algorithm.
|
>
|
![R := PolynomialRing([x, y, z])](/support/helpjp/helpview.aspx?si=4974/file02701/math499.png)
|
|
| (18) |
|
>
|
|
|
| (19) |
|
>
|
|
|
![[regular_chain]](/support/helpjp/helpview.aspx?si=4974/file02701/math516.png)
| (20) |
|
|
|
References
|
|
|
|
Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties." MEGA-2000 conference. Bath, UK, England.
|
|
|
