% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\LexTriangularPackageXmpTitle}{LexTriangularPackage}
\newcommand{\LexTriangularPackageXmpNumber}{9.39}
%
% =====================================================================
\begin{page}{LexTriangularPackageXmpPage}{9.39 LexTriangularPackage}
% =====================================================================
\beginscroll
The \spadtype{LexTriangularPackage} package constructor provides an implementation
of the {\em 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 {\bf R} of the polynomials,
which must be a \spadtype{GcdDomain}
and their set of variables given by {\bf ls} a \spadtype{List Symbol}.
The type of the input polynomials must be \spadtype{NewSparseMultivariatePolynomial(R,V)}
where {\bf V} is \spadtype{OrderedVariableList(ls)}.
The abbreviation for \spadtype{LexTriangularPackage} is \spadtype{LEXTRIPK}.
The main operations are \axiomOpFrom{lexTriangular}{LexTriangularPackage}
and \axiomOpFrom{squareFreeLexTriangular}{LexTriangularPackage}.
The later provide decompositions by means of square-free regular triangular sets,
built with the \spadtype{SREGSET} constructor,
whereas the former uses the \spadtype{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 {\em lexTriangular} algorithm
provided in the \spadtype{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 \axiomOpFrom{squareFreeLexTriangular}{LexTriangularPackage} operation
removes all multiplicities of the solutions (i.e. the computed solutions
are pairwise different) and the \axiomOpFrom{lexTriangular}{LexTriangularPackage}
operation may keep some multiplicities; this later operation runs generally faster
than the former. 

The interest of the {\em 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 \spadtype{SREGSET}
and \spadtype{REGSET}).
This happens typically when the total degree of the system
relies essentially on its smallest variable (like in the
{\em Katsura} systems).
When this is not the case, the direct method may give better timings
(like in the {\em Rose} system).

Of course, the direct method can also be applied to a
lexicographical Groebner basis.
However, the {\em 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 \spadtype{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 \spadtype{RegularTriangularSet}
constructor.

Since the \spadtype{LEXTRIPK} package constructor is limited 
to zero-dimensional systems, it provides a
\axiomOpFrom{zeroDimensional?}{LexTriangularPackage}
operation to check whether this requirement holds.
There is also a \axiomOpFrom{groebner}{LexTriangularPackage}
operation to compute the lexicographical Groebner basis
of a set of polynomials with type \spadtype{NewSparseMultivariatePolynomial(R,V)}.
The elimination ordering is that given by {\bf ls}
(the greatest variable being the first element of {\bf ls}).
This basis is computed by the {\em FLGM} algorithm 
(Faugere et al. "Efficient Computation of Zero-Dimensional Groebner Bases by 
        Change of Ordering" , J. of Symbol. Comput., 1993)
implemented in the \spadtype{LinGroebnerPackage} package constructor.
Once a lexicographical Groebner basis is computed,
then one can call the operations \axiomOpFrom{lexTriangular}{LexTriangularPackage}
and \axiomOpFrom{squareFreeLexTriangular}{LexTriangularPackage}.
Note that these operations admit an optional argument
to produce normalized triangular sets.
There is also a \axiomOpFrom{zeroSetSplit}{LexTriangularPackage} 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 \spadtype{LEXTRIPK} constructor
by a famous example, the {\em cyclic-6 root} system.
\xtc{
Define the coefficient ring.
}{
\spadpaste{R := Integer \bound{R}}
}
\xtc{
Define the list of variables,
}{
\spadpaste{ls : List Symbol := [a,b,c,d,e,f] \bound{ls}}
}
\xtc{
and make it an ordered set.
}{
\spadpaste{V := OVAR(ls) \free{ls} \bound{V}}
}
\xtc{
Define the polynomial ring.
}{
\spadpaste{P := NSMP(R, V) \free{R} \free{V} \bound{P}}
}
\xtc{
Define the polynomials.
}{
\spadpaste{p1: P :=  a*b*c*d*e*f - 1 \free{P} \bound{p1}}
}
\xtc{
}{
\spadpaste{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  \free{P} \bound{p2}}
}
\xtc{
}{
\spadpaste{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 \free{P} \bound{p3}}
}
\xtc{
}{
\spadpaste{p4: P := a*b*c + a*b*f + a*e*f + b*c*d + c*d*e + d*e*f  \free{P} \bound{p4}}
}
\xtc{
}{
\spadpaste{p5: P := a*b + a*f + b*c + c*d + d*e + e*f \free{P} \bound{p5}}
}
\xtc{
}{
\spadpaste{p6: P := a + b + c + d + e + f  \free{P} \bound{p6}}
}
\xtc{
}{
\spadpaste{lp := [p1, p2, p3, p4, p5, p6] \free{p1} \free{p2} \free{p3} \free{p4} \free{p5} \free{p6} \bound{lp}}
}
\xtc{
Now call \spadtype{LEXTRIPK} .
}{
\spadpaste{lextripack :=  LEXTRIPK(R,ls) \free{R} \free{ls} \bound{lextripack}}
}
\xtc{
Compute the lexicographical Groebner basis of the system.
This may take between 5 minutes and one hour, depending on your machine.
}{
\spadpaste{lg := groebner(lp)$lextripack \free{lp} \free{lextripack} \bound{lg}}
}
\xtc{
Apply lexTriangular to compute a decomposition into regular triangular sets.
This should not take more than 5 seconds.
}{
\spadpaste{lexTriangular(lg,false)$lextripack \free{lg} \free{lextripack}}
}
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 \spadtype{NormalizedTriangularSetCategory} constructor).
\xtc{
So apply now lexTriangular to produce normalized triangular sets.
}{
\spadpaste{lts := lexTriangular(lg,true)$lextripack \free{lg} \free{lextripack} \bound{lts}}
}
\xtc{
We check that all initials are constant.
}{
\spadpaste{[[init(p) for p in (ts :: List(P))] for ts in lts]  \free{lts}}
}
Note that each triangular set in {\bf lts} is a lexicographical Groebner basis.
Recall that a point belongs to the variety associated with {\bf lp} if and only if
it belongs to that associated with one triangular set {\bf ts} in {\bf lts}.

By running the \axiomOpFrom{squareFreeLexTriangular}{LexTriangularPackage} operation,
we retrieve the above decomposition.
\xtc{
}{
\spadpaste{squareFreeLexTriangular(lg,true)$lextripack \free{lg} \free{lextripack}}
}
Thus the solutions given by {\bf lts} are pairwise different.
\xtc{
We count them as follows.
}{
\spadpaste{reduce(+,[degree(ts) for ts in lts]) \free{lts}}
}

We can investigate the triangular decomposition {\bf lts} by
using the \spadtype{ZeroDimensionalSolvePackage}.
\xtc{
This requires to add an extra variable (smaller than the others) as follows.
}{
\spadpaste{ls2 : List Symbol := concat(ls,new()$Symbol) \free{ls} \bound{ls2}}
}

\xtc{
Then we call the package.
}{
\spadpaste{zdpack := ZDSOLVE(R,ls,ls2) \free{R} \free{ls} \free{ls2} \bound{zdpack}}
}


\xtc{
We compute a univariate representation of the variety associated with the input
system as follows.
}{
\spadpaste{concat [univariateSolve(ts)$zdpack for ts in lts] \free{lts} \free{zdpack}}
}
Since the \axiomOpFrom{univariateSolve}{ZeroDimensionalSolvePackage} operation may
split a regular set, it returns a list. This explains the use
of \axiomOpFrom{concat}{List}.

Look at the last item of the result. It consists of two parts.
For any complex root {\bf ?} of the univariate polynomial in the first part,
we get a tuple of univariate polynomials (in {\bf a}, ..., {\bf f} respectively)
by replacing {\bf \%A} by {\bf ?} in the second part.
Each of these tuples {\bf t} describes a point of the variety associated with {\bf lp}
by equaling to zero the polynomials in {\bf t}.

Note that the way of reading these univariate representations is explained also
in the example illustrating the \spadtype{ZeroDimensionalSolvePackage} constructor.

\xtc{
Now, we compute the points of the variety with real coordinates.
}{
\spadpaste{concat [realSolve(ts)$zdpack for ts in lts] \free{lts} \free{zdpack}}
}
We obtain 24 points given by lists of elements in the \spadtype{RealClosure}
of \spadtype{Fraction} of {\bf R}.
In each list, the first value corresponds to the indeterminate {\bf f},
the second to {\bf e} and so on.
See \spadtype{ZeroDimensionalSolvePackage} to learn more about
the \axiomOpFrom{realSolve}{ZeroDimensionalSolvePackage} operation.







\endscroll
\autobuttons
\end{page}
%