% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\LazardSetSolvingPackageXmpTitle}{LazardSetSolvingPackage}
\newcommand{\LazardSetSolvingPackageXmpNumber}{9.40}
%
% =====================================================================
\begin{page}{LazardSetSolvingPackageXmpPage}{9.40 LazardSetSolvingPackage}
% =====================================================================
\beginscroll
The \spadtype{LazardSetSolvingPackage} package constructor solves 
polynomial systems by means of Lazard triangular sets.
However one condition is relaxed:
Regular triangular sets whose saturated ideals have positive dimension
are not necessarily normalized.

The decompositions are computed in two steps.
First the algorithm of Moreno Maza (implemented in 
the \spadtype{RegularTriangularSet} domain constructor)
is called.
Then the resulting decompositions are converted into lists 
of square-free regular triangular sets
and the redundant components are removed.
Moreover, zero-dimensional regular triangular sets are normalized.

Note that the way of understanding triangular decompositions 
is detailed in the example of the \spadtype{RegularTriangularSet}
constructor.

The \spadtype{LazardSetSolvingPackage} constructor takes six arguments.
The first one, {\bf R}, is the coefficient ring of the polynomials;
it must belong to the category \spadtype{GcdDomain}.
The second one, {\bf E}, is the exponent monoid of the polynomials;
it must belong to the category \spadtype{OrderedAbelianMonoidSup}.
the third one, {\bf V}, is the ordered set of variables;
it must belong to the category \spadtype{OrderedSet}.
The fourth one is the polynomial ring;
it must belong to the category \spadtype{RecursivePolynomialCategory(R,E,V)}.
The fifth one is a domain of the category \spadtype{RegularTriangularSetCategory(R,E,V,P)}
and the last one is a domain of the category \spadtype{SquareFreeRegularTriangularSetCategory(R,E,V,P)}.
The abbreviation for \spadtype{LazardSetSolvingPackage} is \spad{LAZM3PK}.

{\bf N.B.} For the purpose of solving zero-dimensional algebraic systems,
see also \spadtype{LexTriangularPackage} and \spadtype{ZeroDimensionalSolvePackage}.
These packages are easier to call than \spad{LAZM3PK}.
Moreover, the \spadtype{ZeroDimensionalSolvePackage} 
package  provides operations
to compute either the complex roots or the real roots.

We illustrate now the use of the \spadtype{LazardSetSolvingPackage} package 
constructor with two examples (Butcher and Vermeer).


\xtc{
Define the coefficient ring.
}{
\spadpaste{R := Integer \bound{R}}
}


\xtc{
Define the list of variables,
}{
\spadpaste{ls : List Symbol := [b1,x,y,z,t,v,u,w] \bound{ls}}
} 

\xtc{
and make it an ordered set;
}{
\spadpaste{V := OVAR(ls) \free{ls} \bound{V}}
}

\xtc{
then define the exponent monoid.
}{
\spadpaste{E := IndexedExponents V \free{V} \bound{E}}
}

\xtc{
Define the polynomial ring.
}{
\spadpaste{P := NSMP(R, V) \free{R} \free{V} \bound{P}}
}

\xtc{
Let the variables be polynomial.
}{
\spadpaste{b1: P := 'b1  \free{P} \bound{b1}}
}
\xtc{
}{
\spadpaste{x: P := 'x \free{P} \bound{x}}
}
\xtc{
}{
\spadpaste{y: P := 'y \free{P} \bound{y}}
}
\xtc{
}{
\spadpaste{z: P := 'z \free{P} \bound{z}}
}
\xtc{
}{
\spadpaste{t: P := 't \free{P} \bound{t}}
}
\xtc{
}{
\spadpaste{u: P := 'u  \free{P} \bound{u}}
}
\xtc{
}{
\spadpaste{v: P := 'v  \free{P} \bound{v}}
}
\xtc{
}{
\spadpaste{w: P := 'w  \free{P} \bound{w}}
}

\xtc{
Now call the \spadtype{RegularTriangularSet} domain constructor.
}{
\spadpaste{T := REGSET(R,E,V,P) \free{R} \free{E} \free{V} \free{P} \bound{T} }
}

\xtc{
Define a polynomial system (the Butcher example).
}{
\spadpaste{p0 := b1 + y + z - t - w \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p0}}
}
\xtc{
}{
\spadpaste{p1 := 2*z*u + 2*y*v + 2*t*w - 2*w**2 - w - 1 \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p1}}
}
\xtc{
}{
\spadpaste{p2 := 3*z*u**2 + 3*y*v**2 - 3*t*w**2 + 3*w**3 + 3*w**2 - t + 4*w \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p2}}
}
\xtc{
}{
\spadpaste{p3 := 6*x*z*v - 6*t*w**2 + 6*w**3 - 3*t*w + 6*w**2 - t + 4*w \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p3}}
}
\xtc{
}{
\spadpaste{p4 := 4*z*u**3+ 4*y*v**3+ 4*t*w**3- 4*w**4 - 6*w**3+ 4*t*w- 10*w**2- w- 1 \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p4}}
}
\xtc{
}{
\spadpaste{p5 := 8*x*z*u*v +8*t*w**3 -8*w**4 +4*t*w**2 -12*w**3 +4*t*w -14*w**2 -3*w -1  \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p5}}
}
\xtc{
}{
\spadpaste{p6 := 12*x*z*v**2+12*t*w**3 -12*w**4 +12*t*w**2 -18*w**3 +8*t*w -14*w**2 -w -1 \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p6}}
}
\xtc{
}{
\spadpaste{p7 := -24*t*w**3 + 24*w**4 - 24*t*w**2 + 36*w**3 - 8*t*w + 26*w**2 + 7*w + 1 \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{p7}}
}
\xtc{
}{
\spadpaste{lp := [p0, p1, p2, p3, p4, p5, p6, p7] \free{p0} \free{p1} \free{p2} \free{p3} \free{p4} \free{p5} \free{p6} \free{p7} \bound{lp}}
}

\xtc{
First of all, let us solve this system in the sense of Lazard by means of the \spadtype{REGSET}
constructor:
}{
\spadpaste{lts := zeroSetSplit(lp,false)$T \free{lp} \free{T} \bound{lts}}
}

\xtc{
We can get the dimensions of each component
of a decomposition as follows.
}{
\spadpaste{[coHeight(ts) for ts in lts] \free{lts}}
}

The first five sets have a simple shape.
However, the last one, which has dimension zero, can be simplified
by using Lazard triangular sets.

\xtc{
Thus we call the \spadtype{SquareFreeRegularTriangularSet} domain constructor,
}{
\spadpaste{ST := SREGSET(R,E,V,P) \free{R} \free{E} \free{V} \free{P} \bound{ST} }
}

\xtc{
and set the \spadtype{LAZM3PK} package constructor to our situation.
}{
\spadpaste{pack := LAZM3PK(R,E,V,P,T,ST) \free{R} \free{E} \free{V} \free{P} \free{T} \free{ST} \bound{pack} }
}

\xtc{
We are ready to solve the system by means of Lazard triangular sets:
}{
\spadpaste{zeroSetSplit(lp,false)$pack \free{lp} \free{pack}}
}

We see the sixth triangular set is {\em nicer} now: 
each one of its polynomials has a constant initial.

We follow with the Vermeer example. The ordering is the usual one
for this system.

\xtc{
Define the polynomial system.
}{
\spadpaste{f0 := (w - v) ** 2 + (u - t) ** 2 - 1 \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{f0}}
}
\xtc{
}{
\spadpaste{f1 := t ** 2 - v ** 3 \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{f1}}
}
\xtc{
}{
\spadpaste{f2 := 2 * t * (w - v) + 3 * v ** 2 * (u - t) \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{f2}}
}
\xtc{
}{
\spadpaste{f3 := (3 * z * v ** 2 - 1) * (2 * z * t - 1) \free{b1} \free{x} \free{y} \free{z} \free{t} \free{u} \free{v} \free{w} \bound{f3}}
}
\xtc{
}{
\spadpaste{lf := [f0, f1, f2, f3] \free{f0} \free{f1} \free{f2} \free{f3} \bound{lf}}
}


\xtc{
First of all, let us solve this system in the sense of Kalkbrener by means of the \spadtype{REGSET}
constructor:
}{
\spadpaste{zeroSetSplit(lf,true)$T \free{lf} \free{T}}
}

We have obtained one regular chain (i.e. regular triangular set) with dimension 1.
This set is in fact a characterist set of the (radical of) of the ideal generated
by the input system {\bf lf}.
Thus we have only the {\em generic points} of the variety associated with {\bf lf}
(for the elimination ordering given by {\bf ls}).

So let us get now a full description of this variety.
\xtc{
Hence, we solve this system in the sense of Lazard by means of the \spadtype{REGSET}
constructor:
}{
\spadpaste{zeroSetSplit(lf,false)$T \free{lf} \free{T}}
}

We retrieve our regular chain of dimension 1 and we get three regular chains
of dimension 0 corresponding to the {\em degenerated cases}.
We want now to simplify these zero-dimensional regular chains
by using Lazard triangular sets.
Moreover, this will allow us to prove that the above decomposition has no redundant component.
{\bf N.B.} Generally, decompositions computed by the \spadtype{REGSET}
constructor do not have redundant components.
However, to be sure that no redundant component occurs one needs to use
the \spadtype{SREGSET} or \spadtype{LAZM3PK} constructors.

\xtc{
So let us solve the input system  in the sense of Lazard by means of the \spadtype{LAZM3PK} constructor:
}{
\spadpaste{zeroSetSplit(lf,false)$pack \free{lf} \free{pack}}
}
Due to square-free factorization, we obtained now four zero-dimensional regular chains.
Moreover, each of them is normalized (the initials are constant).
Note that these zero-dimensional components may be investigated further
with the \spadtype{ZeroDimensionalSolvePackage} package constructor.



\endscroll
\autobuttons
\end{page}
%