Initial population.

1 files changed, 432 insertions, 0 deletions

diff --git a/src/hyper/pages/REGSET.ht b/src/hyper/pages/REGSET.ht
new file mode 100644
index 00000000..90a6674c
--- /dev/null
+++ b/src/hyper/pages/REGSET.ht
@@ -0,0 +1,432 @@
+% 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}
+%