next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
TriangularSets :: triangularize

triangularize -- triangular decomposition of polynomial systems

Synopsis

Description

Computes a triangular decomposition of a polynomial system. The package implements algorithms for monomial and binomial sets. For arbitrary systems we interface to Maple.

A polynomial system is a pair (F,H), where F⊂k[x] is a list of equations and and H⊂k[x] is a list of inequations. The zero set of the system is

Z(F/H) = {x : f(x)= 0 for f∈F, h(x)≠0 for h∈H}.

A triangular decomposition of (F,H) is a collection of "simpler" polynomial systems (T1,U1),...,(Tr,Ur) such that

Z(F/H) = Z(T1/U1)∪…∪Z(Tr/Ur).

These simpler sets, called triangular systems, have very nice algorithmic properties.

As a first example we consider a case without inequations (H=Ø).

i1 : R = QQ[a..h, MonomialOrder=>Lex];
i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};
i3 : TT = triangularize(R,F,{})

o3 = {{c, d, f, h}, {b, d, e, f}, {a*d - b*c, e, f} / d, {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}, {c, d, e*h - f*g} / h,
     ----------------------------------------------------------------------------------------------------------------------------
     {c, d, e, f}, {a*d - b*c, c*f - d*e, g, h} / {d, f}, {b, d, f, h}, {c, d, g, h}}

o3 : List
i4 : first TT

o4 = {c, d, f, h}

o4 : TriaSystem

We now include some inequations.

i5 : H = {b,d};
i6 : triangularize(R,F,H)

o6 = {{a*d - b*c, c*f - d*e, g, h} / {b, d, f}, {a*d - b*c, c*f - d*e, e*h - f*g} / {b, d, f, h}, {a*d - b*c, e, f} / {b, d}}

o6 : List

      

See also

Ways to use triangularize :