9.39 LexTriangularPackage¶

The LexTriangularPackage package constructor provides an implementation of the lexTriangular algorithm (D. Lazard Solving Zero-dimensional Algebraic Systems, J. of Symbol. Comput., 1992). This algorithm decomposes a zero-dimensional variety into zero-sets of regular triangular sets. Thus the input system must have a finite number of complex solutions. Moreover, this system needs to be a lexicographical Groebner basis.

This package takes two arguments: the coefficient-ring R of the polynomials, which must be a GcdDomain and their set of variables given by ls a List Symbol. The type of the input polynomials must be NewSparseMultivariatePolynomial(R,V) where V is OrderedVariableList(ls). The abbreviation for LexTriangularPackage is LEXTRIPK. The main operations are lexTriangularlexTriangularLexTriangularPackage and squareFreeLexTriangularsquareFreeLexTriangularLexTriangularPackage. The later provide decompositions by means of square-free regular triangular sets, built with the SREGSET constructor, whereas the former uses the REGSET constructor. Note that these constructors also implement another algorithm for solving algebraic systems by means of regular triangular sets; in that case no computations of Groebner bases are needed and the input system may have any dimension (i.e. it may have an infinite number of solutions).

The implementation of the lexTriangular algorithm provided in the LexTriangularPackage constructor differs from that reported in Computations of gcd over algebraic towers of simple extensions by M. Moreno Maza and R. Rioboo (in proceedings of AAECC11, Paris, 1995). Indeed, the squareFreeLexTriangularsquareFreeLexTriangularLexTriangularPackage operation removes all multiplicities of the solutions (i.e. the computed solutions are pairwise different) and the lexTriangularlexTriangularLexTriangularPackage operation may keep some multiplicities; this later operation runs generally faster than the former.

The interest of the lexTriangular algorithm is due to the following experimental remark. For some examples, a triangular decomposition of a zero-dimensional variety can be computed faster via a lexicographical Groebner basis computation than by using a direct method (like that of SREGSET and REGSET). This happens typically when the total degree of the system relies essentially on its smallest variable (like in the Katsura systems). When this is not the case, the direct method may give better timings (like in the Rose system).

Of course, the direct method can also be applied to a lexicographical Groebner basis. However, the lexTriangular algorithm takes advantage of the structure of this basis and avoids many unnecessary computations which are performed by the direct method.

For this purpose of solving algebraic systems with a finite number of solutions, see also the ZeroDimensionalSolvePackage. It allows to use both strategies (the lexTriangular algorithm and the direct method) for computing either the complex or real roots of a system.

Note that the way of understanding triangular decompositions is detailed in the example of the RegularTriangularSet constructor.

Since the LEXTRIPK package constructor is limited to zero-dimensional systems, it provides a zeroDimensional?zeroDimensional?LexTriangularPackage operation to check whether this requirement holds. There is also a groebnergroebnerLexTriangularPackage operation to compute the lexicographical Groebner basis of a set of polynomials with type NewSparseMultivariatePolynomial(R,V). The elimination ordering is that given by ls (the greatest variable being the first element of ls). This basis is computed by the FLGM algorithm (Faugere et al. Efficient Computation of Zero-Dimensional Groebner Bases by Change of Ordering , J. of Symbol. Comput., 1993) implemented in the LinGroebnerPackage package constructor. Once a lexicographical Groebner basis is computed, then one can call the operations lexTriangularlexTriangularLexTriangularPackage and squareFreeLexTriangularsquareFreeLexTriangularLexTriangularPackage. Note that these operations admit an optional argument to produce normalized triangular sets. There is also a zeroSetSplitzeroSetSplitLexTriangularPackage operation which does all the job from the input system; an error is produced if this system is not zero-dimensional.

Let us illustrate the facilities of the LEXTRIPK constructor by a famous example, the cyclic-6 root system.

Define the coefficient ring.

R := Integer

\[\]

Integer

_{Type: Domain}

Define the list of variables,

ls : List Symbol := [a,b,c,d,e,f]

\[\]

[a,b,c,d,e,f]

_{Type: List Symbol}

and make it an ordered set.

V := OVAR(ls)

\[\]

OrderedVariableList[a,b,c,d,e,f]

_{Type: Domain}

Define the polynomial ring.

P := NSMP(R, V)

\[\]

NewSparseMultivariatePolynomial(Integer,OrderedVariableList[a,b,c,d,e,f])

_{Type: Domain}

Define the polynomials.

p1: P := a*b*c*d*e*f - 1

\[\]

fedcba-1