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

% 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}
%