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.
Type: Domain
Define the list of variables,
ls : List Symbol := [a,b,c,d,e,f]
Type: List Symbol
and make it an ordered set.
|
Type: Domain
Define the polynomial ring.
|
Type: Domain
Define the polynomials.
Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
p2: P := a*b*c*d*e +a*b*c*d*f +a*b*c*e*f +a*b*d*e*f +a*c*d*e*f +b*c*d*e*f
|
Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
p3: P := a*b*c*d + a*b*c*f + a*b*e*f + a*d*e*f + b*c*d*e + c*d*e*f
|
Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
p4: P := a*b*c + a*b*f + a*e*f + b*c*d + c*d*e + d*e*f
Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
p5: P := a*b + a*f + b*c + c*d + d*e + e*f
Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
p6: P := a + b + c + d + e + f
Type: NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
lp := [p1, p2, p3, p4, p5, p6]
|
Type: List NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
Now call LEXTRIPK .
lextripack := LEXTRIPK(R,ls)
|
Type: Domain
Compute the lexicographical Groebner basis of the system.
This may take between 5 minutes and one hour, depending on your machine.
lg := groebner(lp)$lextripack
|
Type: List NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
Apply lexTriangular to compute a decomposition into regular triangular sets.
This should not take more than 5 seconds.
lexTriangular(lg,false)$lextripack
|
Type: List RegularChain(Integer,[a,b,c,d,e,f])
Note that the first set of the decomposition is normalized (all
initials are integer numbers) but not the second one (normalized
triangular sets are defined in the description of the
NormalizedTriangularSetCategory constructor).
So apply now lexTriangular to produce normalized triangular sets.
lts := lexTriangular(lg,true)$lextripack
|
Type: List RegularChain(Integer,[a,b,c,d,e,f])
We check that all initials are constant.
[ [init(p) for p in (ts :: List(P))] for ts in lts]
|
Type: List List NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f])
Note that each triangular set in lts is a lexicographical
Groebner basis. Recall that a point belongs to the variety associated
with lp if and only if it belongs to that associated with one
triangular set ts in lts.
By running the squareFreeLexTriangularsquareFreeLexTriangularLexTriangularPackage
operation, we retrieve the above decomposition.
squareFreeLexTriangular(lg,true)$lextripack
|
Type: List SquareFreeRegularTriangularSet(Integer,IndexedExponents OrderedVariableList [a,b,c,d,e,f],OrderedVariableList [a,b,c,d,e,f],NewSparseMultivariatePolynomial(Integer,OrderedVariableList [a,b,c,d,e,f]))
Thus the solutions given by lts are pairwise different.
We count them as follows.
reduce(+,[degree(ts) for ts in lts])
Type: PositiveInteger
We can investigate the triangular decomposition lts by using the
ZeroDimensionalSolvePackage.
This requires to add an extra variable (smaller than the others) as follows.
ls2 : List Symbol := concat(ls,new()$Symbol)
Type: List Symbol
Then we call the package.
zdpack := ZDSOLVE(R,ls,ls2)
|
Type: Domain
We compute a univariate representation of the variety associated with
the input system as follows.
concat [univariateSolve(ts)$zdpack for ts in lts]
|
Type: List Record(complexRoots: SparseUnivariatePolynomial Integer,coordinates: List Polynomial Integer)
Since the univariateSolveunivariateSolveZeroDimensionalSolvePackage
operation may split a regular set, it returns a list. This explains
the use of concatconcatList.
Look at the last item of the result. It consists of two parts. For
any complex root ? of the univariate polynomial in the first
part, we get a tuple of univariate polynomials (in a, ...,
f respectively) by replacing %A by ? in the second part.
Each of these tuples t describes a point of the variety
associated with lp by equaling to zero the polynomials in t.
Note that the way of reading these univariate representations is explained also
in the example illustrating the ZeroDimensionalSolvePackage constructor.
Now, we compute the points of the variety with real coordinates.
concat [realSolve(ts)$zdpack for ts in lts]
|
Type: List List RealClosure Fraction Integer
We obtain 24 points given by lists of elements in the RealClosure
of Fraction of R. In each list, the first value corresponds
to the indeterminate f, the second to e and so on. See
ZeroDimensionalSolvePackage to learn more about the
realSolverealSolveZeroDimensionalSolvePackage operation.