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 $\left[1\right]$.

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](..).

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.

$\mathrm{with}\left(\mathrm{RegularChains}\right)\:$

$R≔\mathrm{PolynomialRing}\left(\left[z\,y\,x\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$\mathrm{sys}≔\left[x^2+y+z-1\,x+y^2+z-1\,x+y+z^2-1\right]$

$\mathrm{sys}≔\left[x^2+y+z-1\,y^2+x+z-1\,z^2+x+y-1\right]$

$\mathrm{dec}≔\mathrm{Triangularize}\left(\mathrm{sys}\,R\right)$

$\mathrm{dec}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right]$

$\mathrm{map}\left(\mathrm{Equations}\,\mathrm{dec}\,R\right)$

$\left[\left[z-x\,y-x\,x^2+2x-1\right]\,\left[z\,y\,x-1\right]\,\left[z\,y-1\,x\right]\,\left[z-1\,y\,x\right]\right]$

$R≔\mathrm{PolynomialRing}\left(\left[x\,y\,a\,b\,c\,d\,g\,h\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$\mathrm{sys}≔\left[ax+by-g\,cx+dy-h\right]$

$\mathrm{sys}≔\left[ax+by-g\,cx+dy-h\right]$

$\mathrm{dec}≔\mathrm{Triangularize}\left(\mathrm{sys}\,R\right)\;$$\mathrm{map}\left(\mathrm{Equations}\,\mathrm{dec}\,R\right)$

$\mathrm{dec}≔\left[\mathrm{regular\_chain}\right]$

$\left[\left[cx+yd-h\,\left(ad-bc\right)y-ah+cg\right]\right]$

$\mathrm{Groebner}:-\mathrm{Solve}\left(\mathrm{sys}\,\left\{a\,b\,c\,d\,g\,h\,x\,y\right\}\right)$

$\left\{\left[\left[-xa-yb+g\,-cx-yd+h\right]\,\mathrm{plex}\left(h\,g\,d\,c\,b\,a\,y\,x\right)\,\varnothing \right]\right\}$

$\mathrm{decl}≔\mathrm{Triangularize}\left(\mathrm{sys}\,R\,\mathrm{output}=\mathrm{lazard}\right)$

$\mathrm{decl}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right]$

$\mathrm{map}\left(\mathrm{Equations}\,\mathrm{decl}\,R\right)$

$\left[\left[cx+dy-h\,\left(da-bc\right)y-ha+cg\right]\,\left[cx+dy-h\,da-bc\,hb-dg\right]\,\left[ax+by-g\,dy-h\,c\right]\,\left[dy-h\,a\,hb-dg\,c\right]\,\left[cx-h\,ha-cg\,b\,d\right]\,\left[ax+by-g\,c\,d\,h\right]\,\left[cx+dy\,da-bc\,g\,h\right]\,\left[by-g\,a\,c\,d\,h\right]\,\left[y\,a\,c\,g\,h\right]\,\left[x\,b\,d\,g\,h\right]\,\left[a\,b\,c\,d\,g\,h\right]\right]$

$\mathrm{nops}\left(\mathrm{decl}\right)$

$11$

$\mathrm{rc}≔\mathrm{decl}\left[1\right]\;$$\mathrm{Equations}\left(\mathrm{rc}\,R\right)\;$$\mathrm{Inequations}\left(\mathrm{rc}\,R\right)$

$\mathrm{rc}≔\mathrm{regular\_chain}$

$\left[cx+dy-h\,\left(da-bc\right)y-ha+cg\right]$

$\left\{c\,da-bc\right\}$

$\left[\mathrm{seq}\left(\left[\mathrm{eq}=\mathrm{Equations}\left(\mathrm{decl}\left[i\right]\,R\right)\,\mathrm{ineq}=\mathrm{Inequations}\left(\mathrm{decl}\left[i\right]\,R\right)\right]\,i=1..\mathrm{nops}\left(\mathrm{decl}\right)\right)\right]$

$\left[\left[\mathrm{eq}=\left[cx+dy-h\,\left(da-bc\right)y-ha+cg\right]\,\mathrm{ineq}=\left\{c\,da-bc\right\}\right]\,\left[\mathrm{eq}=\left[cx+dy-h\,da-bc\,hb-dg\right]\,\mathrm{ineq}=\left\{c\,d\,h\right\}\right]\,\left[\mathrm{eq}=\left[ax+by-g\,dy-h\,c\right]\,\mathrm{ineq}=\left\{a\,d\right\}\right]\,\left[\mathrm{eq}=\left[dy-h\,a\,hb-dg\,c\right]\,\mathrm{ineq}=\left\{d\,h\right\}\right]\,\left[\mathrm{eq}=\left[cx-h\,ha-cg\,b\,d\right]\,\mathrm{ineq}=\left\{c\,h\right\}\right]\,\left[\mathrm{eq}=\left[ax+by-g\,c\,d\,h\right]\,\mathrm{ineq}=\left\{a\right\}\right]\,\left[\mathrm{eq}=\left[cx+dy\,da-bc\,g\,h\right]\,\mathrm{ineq}=\left\{c\,d\right\}\right]\,\left[\mathrm{eq}=\left[by-g\,a\,c\,d\,h\right]\,\mathrm{ineq}=\left\{b\right\}\right]\,\left[\mathrm{eq}=\left[y\,a\,c\,g\,h\right]\,\mathrm{ineq}=\varnothing \right]\,\left[\mathrm{eq}=\left[x\,b\,d\,g\,h\right]\,\mathrm{ineq}=\varnothing \right]\,\left[\mathrm{eq}=\left[a\,b\,c\,d\,g\,h\right]\,\mathrm{ineq}=\varnothing \right]\right]$

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

$\mathrm{R2}≔\mathrm{polynomial\_ring}$

$\mathrm{dec2}≔\mathrm{Triangularize}\left(\mathrm{sys}\,\mathrm{R2}\,\mathrm{output}=\mathrm{lazard}\right)$

$\mathrm{dec2}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right]$

$\left[\mathrm{seq}\left(\left[\mathrm{eq}=\mathrm{Equations}\left(\mathrm{dec2}\left[i\right]\,\mathrm{R2}\right)\,\mathrm{ineq}=\mathrm{Inequations}\left(\mathrm{dec2}\left[i\right]\,\mathrm{R2}\right)\right]\,i=1..\mathrm{nops}\left(\mathrm{dec2}\right)\right)\right]$

$\left[\left[\mathrm{eq}=\left[cx+dy-h\,\left(da-bc\right)y-ha+cg\right]\,\mathrm{ineq}=\left\{c\,da-bc\right\}\right]\,\left[\mathrm{eq}=\left[cx+dy-h\,da-bc\,hb-dg\right]\,\mathrm{ineq}=\left\{c\,d\right\}\right]\,\left[\mathrm{eq}=\left[ax+yb-g\,dy-h\,c\right]\,\mathrm{ineq}=\left\{a\,d\right\}\right]\,\left[\mathrm{eq}=\left[dy-h\,a\,hb-dg\,c\right]\,\mathrm{ineq}=\left\{d\right\}\right]\,\left[\mathrm{eq}=\left[cx-h\,ha-cg\,b\,d\right]\,\mathrm{ineq}=\left\{c\right\}\right]\right]$

$\mathrm{nops}\left(\mathrm{dec2}\right)$

$5$

$R≔\mathrm{PolynomialRing}\left(\left[x\,y\,z\right]\right)$

$R≔\mathrm{polynomial\_ring}$

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

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

$\mathrm{Triangularize}\left(\mathrm{sys}\,R\,\mathrm{probability}=0.9\right)$

$\left[\mathrm{regular\_chain}\right]$

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