Initial population.

1 files changed, 269 insertions, 0 deletions

diff --git a/src/hyper/pages/ZDSOLVE.ht b/src/hyper/pages/ZDSOLVE.ht
new file mode 100644
index 00000000..fb7ece3f
--- /dev/null
+++ b/src/hyper/pages/ZDSOLVE.ht
@@ -0,0 +1,269 @@
+% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
+% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
+\newcommand{\ZeroDimensionalSolvePackageXmpTitle}{ZeroDimensionalSolvePackage}
+\newcommand{\ZeroDimensionalSolvePackageXmpNumber}{9.91}
+%
+% =====================================================================
+\begin{page}{ZeroDimensionalSolvePackageXmpPage}{9.91 ZeroDimensionalSolvePackage}
+% =====================================================================
+\beginscroll
+The \spadtype{ZeroDimensionalSolvePackage} package constructor 
+provides operations for computing symbolically the complex or real roots of 
+zero-dimensional algebraic systems.
+
+The package provides {\bf no} multiplicity information (i.e. some returned
+roots may be double or higher) but only distinct roots are returned. 
+
+Complex roots are given by means of univariate representations
+of irreducible regular chains. 
+These representations are computed by the \axiomOpFrom{univariateSolve}{ZeroDimensionalSolvePackage}
+operation (by calling the \spadtype{InternalRationalUnivariateRepresentationPackage} 
+package constructor which does the job).
+
+Real roots are given by means of tuples
+of coordinates lying in the \spadtype{RealClosure} of the coefficient ring.
+They are computed by the \axiomOpFrom{realSolve}{ZeroDimensionalSolvePackage}
+and \axiomOpFrom{positiveSolve}{ZeroDimensionalSolvePackage} operations.
+The former computes all the solutions of the input system with real coordinates
+whereas the later concentrate on the solutions with (strictly) positive coordinates.
+In both cases, the computations are performed by the \spadtype{RealClosure} constructor.
+
+Both computations of complex roots and real roots rely on triangular decompositions.
+These decompositions can be computed in two different ways.
+First, by a applying the \axiomOpFrom{zeroSetSplit}{RegularTriangularSet} 
+operation from the \spadtype{REGSET} domain constructor.
+In that case, no Groebner bases are computed.
+This strategy is used by default.
+Secondly, by applying the \axiomOpFrom{zeroSetSplit}{LexTriangularPackage}
+from \spadtype{LEXTRIPK}.
+To use this later strategy with the operations
+\axiomOpFrom{univariateSolve}{ZeroDimensionalSolvePackage},
+\axiomOpFrom{realSolve}{ZeroDimensionalSolvePackage}
+and \axiomOpFrom{positiveSolve}{ZeroDimensionalSolvePackage} 
+one just needs to use an extra boolean argument.
+
+Note that the way of understanding triangular decompositions 
+is detailed in the example of the \spadtype{RegularTriangularSet}
+constructor.
+
+The \spadtype{ZeroDimensionalSolvePackage} constructor takes three arguments. 
+The first one {\bf R} is the coefficient ring;
+it must belong to the categories
+\spadtype{OrderedRing}, \spadtype{EuclideanDomain},  \spadtype{CharacteristicZero}
+and \spadtype{RealConstant}.
+This means essentially that {\bf R} is \spadtype{Integer} or \spadtype{Fraction(Integer)}.
+The second argument {\bf ls} is the list of variables involved 
+in the systems to solve. 
+The third one MUST BE {\bf concat(ls,s)} where
+{\bf s} is an additional symbol used for the univariate representations.
+The abbreviation for \spadtype{ZeroDimensionalSolvePackage} is \spadtype{ZDSOLVE}.
+
+We illustrate now how to use the constructor \spadtype{ZDSOLVE}
+by two examples: the {\em Arnborg and Lazard} system and the {\em L-3} system (Aubry and Moreno Maza).
+Note that the use of this package is also demonstrated in the example
+of the \spadtype{LexTriangularPackage} constructor.
+
+\xtc{
+Define the coefficient ring.
+}{
+\spadpaste{R := Integer \bound{R}}
+}
+
+\xtc{
+Define the lists of variables:
+}{
+\spadpaste{ls : List Symbol := [x,y,z,t] \bound{ls}}
+}
+
+\xtc{
+and:
+}{
+\spadpaste{ls2 : List Symbol := [x,y,z,t,new()$Symbol] \bound{ls2}}
+}
+
+\xtc{
+Call the package:
+}{
+\spadpaste{pack := ZDSOLVE(R,ls,ls2) \free{ls} \free{ls2} \free{R} \bound{pack}}
+}
+
+\xtc{
+Define a polynomial system (Arnborg-Lazard)
+}{
+\spadpaste{p1 := x**2*y*z + x*y**2*z + x*y*z**2 + x*y*z + x*y + x*z + y*z \bound{p1}}
+}
+\xtc{
+}{
+\spadpaste{p2 := x**2*y**2*z + x*y**2*z**2 + x**2*y*z + x*y*z + y*z + x + z \bound{p2}}
+}
+\xtc{
+}{
+\spadpaste{p3 := x**2*y**2*z**2 + x**2*y**2*z + x*y**2*z + x*y*z + x*z + z + 1 \bound{p3}}
+}
+\xtc{
+}{
+\spadpaste{lp := [p1, p2, p3] \free{p1} \free{p2} \free{p3} \bound{lp}}
+}
+Note that these polynomials do not involve the variable {\bf t};
+we will use it in the second example.
+
+\xtc{
+First compute a decomposition into regular chains (i.e. regular triangular sets).
+}{
+\spadpaste{triangSolve(lp)$pack \free{lp} \free{pack}}
+}
+
+We can see easily from this decomposition (consisting of a single
+regular chain) that the input system has 20 complex roots.
+
+\xtc{
+Then we compute a univariate representation of this regular chain.
+}{
+\spadpaste{univariateSolve(lp)$pack \free{lp} \free{pack}}
+}
+
+We see that the zeros of our regular chain are split into three components.
+This is due to the use of univariate polynomial factorization.
+
+Each of these components consist of two parts.
+The first one is an irreducible univariate polynomial {\bf p(?)} which defines
+a simple algebraic extension of the field of fractions of {\bf R}.
+The second one consists of multivariate polynomials {\bf pol1(x,\%A)},
+{\bf pol2(y,\%A)} and {\bf pol3(z,\%A)}.
+Each of these polynomials involve two variables: one is an indeterminate
+{\bf x}, {\bf y} or {\bf z}
+of the input system {\bf lp} and the other is {\bf \%A} which represents any root of {\bf p(?)}.
+Recall that this {\bf \%A} is the last element of the third parameter of 
+\spadtype{ZDSOLVE}.
+Thus any complex root {\bf ?} of {\bf p(?)} leads to a solution of the input system {\bf lp} 
+by replacing {\bf \%A} by this {\bf ?} in {\bf pol1(x,\%A)},
+{\bf pol2(y,\%A)} and {\bf pol3(z,\%A)}.
+Note that the polynomials {\bf pol1(x,\%A)},
+{\bf pol2(y,\%A)} and {\bf pol3(z,\%A)} have degree one 
+w.r.t. {\bf x}, {\bf y} or {\bf z} respectively.
+This is always the case for all univariate representations.
+Hence the operation {\bf univariateSolve} replaces a
+system of multivariate polynomials by a list of univariate
+polynomials, what justifies its name.
+Another example of univariate representations illustrates
+the \spadtype{LexTriangularPackage} package constructor.
+
+\xtc{
+We now compute the solutions with real coordinates:
+}{
+\spadpaste{lr := realSolve(lp)$pack \free{lp} \free{pack} \bound{lr}}
+}
+
+\xtc{
+The number of real solutions for the input system is:
+}{
+\spadpaste{\# lr \free{lr}}
+}
+
+Each of these real solutions is given by a list of elements in  \spadtype{RealClosure(R)}.
+In these 8 lists, the first element is a value of {\bf z}, 
+the second of {\bf y} and the last of {\bf x}.
+This is logical since by setting the list of variables of the package
+to {\bf [x,y,z,t]} we mean that the elimination ordering on the
+variables is {\bf t < z < y < x }.
+Note that each system treated by the \spadtype{ZDSOLVE} package constructor
+needs only to be zero-dimensional w.r.t. the variables involved in the system it-self
+and not necessarily w.r.t. all the variables used to define the package.
+
+\xtc{
+We can approximate these real numbers as follows. 
+This computation takes between 30 sec. and 5 min, depending on your machine.
+}{
+\spadpaste{[[approximate(r,1/1000000) for r in point] for point in lr] \free{lr}}
+}
+
+\xtc{
+We can also concentrate on the solutions with real (strictly) positive coordinates:
+}{
+\spadpaste{lpr := positiveSolve(lp)$pack \free{lp} \free{pack} \bound{lpr}}
+}
+
+Thus we have checked that the input system has no solution with strictly positive coordinates.
+
+
+\xtc{
+Let us define another polynomial system ({\em L-3}).
+}{
+\spadpaste{f0 := x**3 + y + z + t- 1 \bound{f0}}
+}
+\xtc{
+}{
+\spadpaste{f1 := x + y**3 + z + t -1 \bound{f1}}
+}
+\xtc{
+}{
+\spadpaste{f2 := x + y + z**3 + t-1 \bound{f2}}
+}
+\xtc{
+}{
+\spadpaste{f3 := x + y + z + t**3 -1 \bound{f3}}
+}
+\xtc{
+}{
+\spadpaste{lf := [f0, f1, f2, f3] \free{f0} \free{f1} \free{f2} \free{f3} \bound{lf}}
+}
+
+
+\xtc{
+First compute a decomposition into regular chains (i.e. regular triangular sets).
+}{
+\spadpaste{lts := triangSolve(lf)$pack \free{lf} \free{pack} \bound{lts}}
+}
+
+
+\xtc{
+Then we compute a univariate representation.
+}{
+\spadpaste{univariateSolve(lf)$pack \free{lf} \free{pack}}
+}
+
+Note that this computation is made from the input system {\bf lf}.
+\xtc{
+However it is possible to reuse a pre-computed regular chain as follows:
+}{
+\spadpaste{ts := lts.1 \free{lts} \bound{ts}}
+}
+\xtc{
+}{
+\spadpaste{univariateSolve(ts)$pack \free{ts} \free{pack}}
+}
+\xtc{
+}{
+\spadpaste{realSolve(ts)$pack  \free{ts} \free{pack}}
+}
+
+\xtc{
+We compute now the full set of points with real coordinates:
+}{
+\spadpaste{lr2 := realSolve(lf)$pack \free{lf} \free{pack}  \bound{lr2}}
+}
+
+
+\xtc{
+The number of real solutions for the input system is:
+}{
+\spadpaste{\#lr2 \free{lr2}}
+}
+Another example of computation of real solutions illustrates
+the \spadtype{LexTriangularPackage} package constructor.
+
+\xtc{
+We concentrate now on the solutions with real (strictly) positive coordinates:
+}{
+\spadpaste{lpr2 := positiveSolve(lf)$pack \free{lf} \free{pack} \bound{lpr2}}
+}
+
+\xtc{
+Finally, we approximate the coordinates of this point with 20 exact digits:
+}{
+\spadpaste{[approximate(r,1/10**21)::Float for r in lpr2.1] \free{lpr2}}
+}
+\endscroll
+\autobuttons
+\end{page}
+%