path: root/src/hyper/pages/REGSET.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\RegularTriangularSetXmpTitle}{RegularTriangularSet}
\newcommand{\RegularTriangularSetXmpNumber}{9.67}
%
% =====================================================================
\begin{page}{RegularTriangularSetXmpPage}{9.67 RegularTriangularSet}
% =====================================================================
\beginscroll
The \spadtype{RegularTriangularSet} domain constructor implements
regular triangular sets.
These particular triangular sets were introduced by M. Kalkbrener (1991) 
in his PhD Thesis under the name regular chains.
Regular chains and their related concepts are presented in
the paper "On the Theories of Triangular sets" By P. Aubry, D. Lazard
and M. Moreno Maza (to appear in the Journal of Symbolic Computation).
The \spadtype{RegularTriangularSet} constructor also provides a new method (by the third author) 
for solving polynomial system by means of regular chains.
This method has two ways of solving.
One has the same specifications as Kalkbrener's algorithm (1991)
and the other is closer to Lazard's method (Discr. App. Math, 1991).
Moreover, this new method removes redundant component from the 
decompositions when this is not {\em too expensive}.
This is always the case with square-free regular chains.
So if you want to obtain decompositions without redundant components
just use the \spadtype{SquareFreeRegularTriangularSet} domain constructor 
or the \spadtype{LazardSetSolvingPackage} package constructor.
See also the \spadtype{LexTriangularPackage} and \spadtype{ZeroDimensionalSolvePackage} for the case of 
algebraic systems with a finite number of (complex) solutions.

One of the main features of regular triangular sets is that they
naturally define towers of simple extensions of a field.
This allows to perform with multivariate polynomials the 
same kind of operations as one can do in an \spadtype{EuclideanDomain}.

The \spadtype{RegularTriangularSet} constructor takes four 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 last one is the polynomial ring;
it must belong to the category \spadtype{RecursivePolynomialCategory(R,E,V)}.
The abbreviation for \spadtype{RegularTriangularSet} is
\spadtype{REGSET}.
See also the constructor \spadtype{RegularChain} which only takes
two arguments, the coefficient ring and the ordered set of variables;
in that case, polynomials are necessarily built with the
\spadtype{NewSparseMultivariatePolynomial}  domain constructor.

We shall explain now how to use the constructor \spadtype{REGSET} 
and how to read the decomposition of a polynomial system by means of regular sets.

Let us give some examples.
We start with an easy one (Donati-Traverso) 
in order to understand the two ways of
solving polynomial systems provided by the \spadtype{REGSET} constructor.
\xtc{
Define the coefficient ring.
}{
\spadpaste{R := Integer \bound{R}}
}
\xtc{
Define the list of variables,
}{
\spadpaste{ls : List Symbol := [x,y,z,t] \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{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{
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.
}{
\spadpaste{p1 := x ** 31 - x ** 6 - x - y \free{x} \free{y} \bound{p1}}
}
\xtc{
}{
\spadpaste{p2 := x ** 8  - z \free{x} \free{z} \bound{p2}}
}
\xtc{
}{
\spadpaste{p3 := x ** 10 - t \free{x} \free{t} \bound{p3}}
}
\xtc{
}{
\spadpaste{lp := [p1, p2, p3] \free{p1} \free{p2} \free{p3} \bound{lp}}
}
\xtc{
First of all, let us solve this system in the sense of Kalkbrener.
}{
\spadpaste{zeroSetSplit(lp)$T \free{lp} \free{T}}
}
\xtc{
And now in the sense of Lazard (or Wu and other authors).
}{
\spadpaste{lts := zeroSetSplit(lp,false)$T \free{lp} \free{T} \bound{lts}}
}

We can see that the first decomposition is a subset of the second.
So how can both be correct ?

Recall first that polynomials from a domain of the category
\spadtype{RecursivePolynomialCategory} are regarded
as univariate polynomials in their main variable.
For instance the second polynomial in the first set
of each decomposition has main variable {\bf y}
and its initial (i.e. its leading coefficient w.r.t. its main
variable) is {\bf t z}.

Now let us explain how to read the second decomposition.
Note that the non-constant initials of the first set are
\texht{$t^4-t$}{{\bf t^4 - t}} and \texht{$t z$}{{\bf t z}}.
Then the solutions described by this first set are the common
zeros of its polynomials that do not cancel the polynomials
\texht{$t^4-t$}{{\bf t^4 - t}} and \texht{$ty z$}{{\bf t z}}.
Now the solutions of the input system {\bf lp} satisfying
these equations are described by the second and the third
sets of the decomposition.
Thus, in some sense, they can be considered as degenerated
solutions.
The solutions given by the first set are called the generic
points of the system; they give the general form of the
solutions.
The first decomposition only provides these generic points.
This latter decomposition is useful when they are many degenerated 
solutions (which is sometimes hard to compute) and when
one is only interested in general informations, like
the dimension of the input system.

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

Thus the first set has dimension one.
Indeed {\bf t} can take any value, except {\bf 0}
or any third root of {\bf 1}, whereas {\bf z}
is completely determined from {\bf t},
{\bf y} is given by {\bf z} and {\bf t},
and finally {\bf x} is given by the other three variables.
In the second and the third sets of the second decomposition
the four variables are completely determined and thus
these sets have dimension zero.

We give now the precise specifications of each decomposition. 
This assume some mathematical knowledge.
However, for the non-expert user, the above explanations will 
be sufficient to understand the other features of the
\spadtype{RSEGSET} constructor.

The input system {\bf lp} is decomposed in the sense
of Kalkbrener as finitely many regular sets {\bf T1,...,Ts}
such that the radical ideal generated by {\bf lp}
is the intersection of the radicals of the
saturated ideals of {\bf T1,...,Ts}.
In other words, the affine variety associated with {\bf lp} 
is the union of the closures (w.r.t. Zarisky topology)
of the regular-zeros sets of {\bf T1,...,Ts}.

{\bf N. B.} The prime ideals associated with the 
radical of the saturated ideal of
a regular triangular set have all the same dimension;
moreover these prime ideals can be given by characteristic
sets with the same main variables. 
Thus a decomposition in the sense of Kalkbrener
is unmixed dimensional.
Then it can be viewed as a {\em lazy}
decomposition into prime ideals (some of these 
prime ideals being merged into unmixed dimensional ideals).

Now we explain the other way of solving by means of regular 
triangular sets.
The input system {\bf lp} is decomposed in the sense
of Lazard as finitely many regular triangular sets {\bf T1,...,Ts}
such that the affine variety associated with {\bf lp}
is the union of the regular-zeros sets of {\bf T1,...,Ts}.
Thus a decomposition in the sense of Lazard is also
a decomposition in the sense of Kalkbrener; the converse
is false as we have seen before.

When the input system has a finite number of solutions,
both ways of solving provide similar decompositions as
we shall see with this second example (Caprasse).


\xtc{
Define a polynomial system.
}{
\spadpaste{f1 := y**2*z+2*x*y*t-2*x-z \free{z} \free{x} \free{y} \free{t} \bound{f1}}
}
\xtc{
}{
\spadpaste{f2 :=   -x**3*z+ 4*x*y**2*z+ 4*x**2*y*t+ 2*y**3*t+ 4*x**2- 10*y**2+ 4*x*z- 10*y*t+ 2 \free{z} \free{x} \free{y} \free{t} \bound{f2}}
}
\xtc{
}{
\spadpaste{f3 :=  2*y*z*t+x*t**2-x-2*z \free{z} \free{x} \free{y} \free{t} \bound{f3}}
}
\xtc{
}{
\spadpaste{f4 :=   -x*z**3+ 4*y*z**2*t+ 4*x*z*t**2+ 2*y*t**3+ 4*x*z+ 4*z**2-10*y*t- 10*t**2+2 \free{z} \free{x} \free{y} \free{t} \bound{f4}}
}
\xtc{
}{
\spadpaste{lf := [f1, f2, f3, f4] \free{f1} \free{f2} \free{f3}  \free{f4} \bound{lf}}
}

\xtc{
First of all, let us solve this system in the sense of Kalkbrener.
}{
\spadpaste{zeroSetSplit(lf)$T \free{lf} \free{T}}
}
\xtc{
And now in the sense of Lazard (or Wu and other authors).
}{
\spadpaste{lts2 := zeroSetSplit(lf,false)$T \free{lf} \free{T} \bound{lts2}}
}

Up to the ordering of the components, both decompositions are identical.

\xtc{
Let us check that each component has a finite number of solutions.
}{
\spadpaste{[coHeight(ts) for ts in lts2] \free{lts2}}
}

\xtc{
Let us count the degrees of each component,
}{
\spadpaste{degrees := [degree(ts) for ts in lts2] \free{lts2} \bound{degrees}}
}
\xtc{
and compute their sum.
}{
\spadpaste{reduce(+,degrees) \free{degrees}}
}

We study now the options of the \spadfun{zeroSetSplit} operation.
As we have seen yet, there is an optional second argument 
which is a boolean value. If this value is true (this
is the default) then the decomposition is computed
in the sense of Kalkbrener, otherwise it is computed
in the sense of Lazard.

There is a second boolean optional argument that
can be used (in that case the first optional
argument must be present).
This second option allows you to get some information
during the computations.

Therefore, we need to understand a little what is 
going on during the computations.
An important feature of the algorithm is that 
the intermediate computations are managed in some sense 
like the processes of a Unix system.
Indeed, each intermediate computation may generate
other intermediate computations and the management
of all these computations is a crucial task for
the efficiency.
Thus any intermediate computation may be suspended,
killed or resumed, depending on algebraic considerations
that determine priorities for these processes.
The goal is of course to go as fast as possible 
towards the final decomposition which means to avoid
as much as possible unnecessary computations.

To follow the computations, one needs to set to
\spad{true} the second argument.
Then a lot of numbers and letters are displayed.
Between a \spad{[} and a \spad{]} one has 
the state of the processes at a given time.
Just after \spad{[} one can see the number of
processes. 
Then each process is represented by two numbers
between \spad{<} and \spad{>}.
A process consists of a list of polynomial {\bf ps}
and a triangular set {\bf ts}; its goal is to compute
the common zeros of {\bf ps} that belong to the
regular-zeros set of {\bf ts}.
After the processes, the number between pipes
gives the total number of polynomials
in all the sets \spad{ps}.
Finally, the number between braces gives the number
of components of a decomposition that are already
computed. This number may decrease.

Let us take a third example (Czapor-Geddes-Wang) to see how these
informations are displayed.

\xtc{
Define a polynomial system.
}{
\spadpaste{u : R := 2  \free{R} \bound{u}}
}
\xtc{
}{
\spadpaste{q1 := 2*(u-1)**2+ 2*(x-z*x+z**2)+ y**2*(x-1)**2- 2*u*x+ 2*y*t*(1-x)*(x-z)+ 2*u*z*t*(t-y)+ u**2*t**2*(1-2*z)+ 2*u*t**2*(z-x)+ 2*u*t*y*(z-1)+ 2*u*z*x*(y+1)+ (u**2-2*u)*z**2*t**2+ 2*u**2*z**2+ 4*u*(1-u)*z+ t**2*(z-x)**2 \free{z} \free{x} \free{y} \free{t} \free{u} \bound{q1}}
}
\xtc{
}{
\spadpaste{q2 := t*(2*z+1)*(x-z)+ y*(z+2)*(1-x)+ u*(u-2)*t+ u*(1-2*u)*z*t+ u*y*(x+u-z*x-1)+ u*(u+1)*z**2*t \free{z} \free{x} \free{y} \free{t} \free{u} \bound{q2}}
}
\xtc{
}{
\spadpaste{q3 := -u**2*(z-1)**2+ 2*z*(z-x)-2*(x-1) \free{z} \free{x} \free{y} \free{t} \free{u}  \bound{q3}}
}
\xtc{
}{
\spadpaste{q4 :=   u**2+4*(z-x**2)+3*y**2*(x-1)**2- 3*t**2*(z-x)**2 +3*u**2*t**2*(z-1)**2+u**2*z*(z-2)+6*u*t*y*(z+x+z*x-1) \free{z} \free{x} \free{y} \free{t} \free{u} \bound{q4}}
}
\xtc{
}{
\spadpaste{lq := [q1, q2, q3, q4] \free{q1} \free{q2} \free{q3}  \free{q4} \bound{lq}}
}


\xtc{
Let us try the information option.
N.B. The timing should be between 1 and 10 minutes, depending on your machine.
}{
\spadpaste{zeroSetSplit(lq,true,true)$T \free{lq} \free{T}}
}

Between a sequence of processes, thus between a \spad{]} and a \spad{[}
you can see capital letters \spad{W, G, I} and lower case letters
\spad{i, w}. Each time a capital letter appears a non-trivial computation
has be performed and its result is put in a hash-table.
Each time a lower case letter appears a needed result has been 
found in an hash-table.
The use of these hash-tables generally speed up the computations.
However, on very large systems, it may happen that these hash-tables
become too  big  to be handle by your AXIOM configuration.
Then in these exceptional cases, you may prefer getting a result
(even if it takes a long time) than getting nothing.
Hence you need to know how to prevent the \spadtype{RSEGSET} constructor
from using these hash-tables.
In that case you will be using the \spadfun{zeroSetSplit} with five arguments.
The first one is the input system {\bf lp} as above.
The second one is a boolean value \spad{hash?} which is \spad{true}
iff you want to use hash-tables.
The third one is boolean value \spad{clos?} which is \spad{true}
iff you want to solve your system in the sense of Kalkbrener,
the other way remaining that of Lazard.
The fourth argument is boolean value \spad{info?} which is \spad{true}
iff you want to display information during the computations.
The last one is boolean value \spad{prep?} which is \spad{true}
iff you want to use some heuristics that are performed on the
input system before starting the real algorithm.
The value of this flag is \spad{true} when you are using \spadfun{zeroSetSplit} 
with less than five arguments.
Note that there is no available signature for \spadfun{zeroSetSplit} with 
four arguments.

We finish this section by some remarks about both ways of
solving, in the sense of Kalkbrener or in the sense of Lazard.
For problems with a finite number of solutions, there are
theoretically equivalent and the resulting decompositions
are identical, up to the ordering of the components.
However, when solving in the sense of Lazard, the algorithm
behaves differently.
In that case, it becomes more incremental than in the sense
of Kalkbrener. That means the polynomials of the input system
are considered one after another whereas in the sense of Kalkbrener
the input system is treated more globally.

This makes an important difference in positive dimension.
Indeed when solving in the sense of Kalkbrener, the
{\em Primeidealkettensatz} of Krull is used.
That means any regular triangular containing more polynomials
than the input system can be deleted.
This is not possible when solving in the sense of Lazard.
This explains why Kalkbrener's decompositions
usually contain less components than those of Lazard.
However, it may happen with some examples that the incremental process
(that cannot be used when solving in the sense of Kalkbrener)
provide a more efficient way of solving than the global one
even if the {\em Primeidealkettensatz} is used.
Thus just try both, with the various options, before concluding 
that you cannot solve your favorite system with \spadfun{zeroSetSplit}.
There exist more options at the development level that are not
currently available in this public version.
So you are welcome to contact {\em marc@nag.co.uk} for more
information and help.








\endscroll
\autobuttons
\end{page}
%