9.91 ZeroDimensionalSolvePackage
The ZeroDimensionalSolvePackage package constructor provides
operations for computing symbolically the complex or real roots of
zero-dimensional algebraic systems.
The package provides 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
univariateSolveunivariateSolveZeroDimensionalSolvePackage operation
(by calling the InternalRationalUnivariateRepresentationPackage
package constructor which does the job).
Real roots are given by means of tuples of coordinates lying in the
RealClosure of the coefficient ring. They are computed by the
realSolverealSolveZeroDimensionalSolvePackage and
positiveSolvepositiveSolveZeroDimensionalSolvePackage 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 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
zeroSetSplitzeroSetSplitRegularTriangularSet operation from the
REGSET domain constructor. In that case, no Groebner bases are
computed. This strategy is used by default. Secondly, by applying
the zeroSetSplitzeroSetSplitLexTriangularPackage from
LEXTRIPK. To use this later strategy with the operations
univariateSolveunivariateSolveZeroDimensionalSolvePackage,
realSolverealSolveZeroDimensionalSolvePackage and
positiveSolvepositiveSolveZeroDimensionalSolvePackage one just
needs to use an extra boolean argument.
Note that the way of understanding triangular decompositions
is detailed in the example of the RegularTriangularSet
constructor.
The ZeroDimensionalSolvePackage constructor takes three
arguments. The first one R is the coefficient ring; it must
belong to the categories OrderedRing, EuclideanDomain,
CharacteristicZero and RealConstant. This means
essentially that R is Integer or Fraction(Integer).
The second argument ls is the list of variables involved in the
systems to solve. The third one MUST BE concat(ls,s) where
s is an additional symbol used for the univariate representations.
The abbreviation for ZeroDimensionalSolvePackage is ZDSOLVE.
We illustrate now how to use the constructor ZDSOLVE by two
examples: the Arnborg and Lazard system and the L-3 system
(Aubry and Moreno Maza). Note that the use of this package is also
demonstrated in the example of the LexTriangularPackage
constructor.
Define the coefficient ring.
Type: Domain
Define the lists of variables:
ls : List Symbol := [x,y,z,t]
Type: List Symbol
and:
ls2 : List Symbol := [x,y,z,t,new()$Symbol]
Type: List Symbol
Call the package:
pack := ZDSOLVE(R,ls,ls2)
|
|
Type: Domain
Define a polynomial system (Arnborg-Lazard)
p1 := x**2*y*z + x*y**2*z + x*y*z**2 + x*y*z + x*y + x*z + y*z
|
|
Type: Polynomial Integer
p2 := x**2*y**2*z + x*y**2*z**2 + x**2*y*z + x*y*z + y*z + x + z
|
|
Type: Polynomial Integer
p3 := x**2*y**2*z**2 + x**2*y**2*z + x*y**2*z + x*y*z + x*z + z + 1
|
|
Type: Polynomial Integer
|
|
Type: List Polynomial Integer
Note that these polynomials do not involve the variable t;
we will use it in the second example.
First compute a decomposition into regular chains (i.e. regular
triangular sets).
|
|
Type: List RegularChain(Integer,[x,y,z,t])
We can see easily from this decomposition (consisting of a single
regular chain) that the input system has 20 complex roots.
Then we compute a univariate representation of this regular chain.
|
|
Type:
List Record(
complexRoots: SparseUnivariatePolynomial Integer,
coordinates: List Polynomial Integer)
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 p(?) which defines a simple
algebraic extension of the field of fractions of R. The second
one consists of multivariate polynomials pol1(x,%A),
pol2(y,%A) and pol3(z,%A). Each of these polynomials involve
two variables: one is an indeterminate x, y or z of
the input system lp and the other is %A which represents
any root of p(?). Recall that this %A is the last
element of the third parameter of ZDSOLVE. Thus any complex
root ? of p(?) leads to a solution of the input system
lp by replacing %A by this ? in pol1(x,%A),
pol2(y,%A) and pol3(z,%A). Note that the polynomials
pol1(x,%A), pol2(y,%A) and pol3(z,%A) have degree
one w.r.t. x, y or z respectively. This is always
the case for all univariate representations. Hence the operation
univariateSolve replaces a system of multivariate polynomials by a
list of univariate polynomials, what justifies its name. Another
example of univariate representations illustrates the
LexTriangularPackage package constructor.
We now compute the solutions with real coordinates:
|
|
Type: List List RealClosure Fraction Integer
The number of real solutions for the input system is:
Type: PositiveInteger
Each of these real solutions is given by a list of elements in
RealClosure(R). In these 8 lists, the first element is a value of
z, the second of y and the last of x. This is
logical since by setting the list of variables of the package to
[x,y,z,t] we mean that the elimination ordering on the variables is
t < z < y < x . Note that each system treated by the
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.
We can approximate these real numbers as follows.
This computation takes between 30 sec. and 5 min, depending on your machine.
[ [approximate(r,1/1000000) for r in point] for point in lr]
|
|
Type: List List Fraction Integer
We can also concentrate on the solutions with real (strictly) positive
coordinates:
lpr := positiveSolve(lp)$pack
Type: List List RealClosure Fraction Integer
Thus we have checked that the input system has no solution with
strictly positive coordinates.
Let us define another polynomial system (L-3).
f0 := x**3 + y + z + t- 1
Type: Polynomial Integer
f1 := x + y**3 + z + t -1
Type: Polynomial Integer
Type: Polynomial Integer
f3 := x + y + z + t**3 -1
Type: Polynomial Integer
|
|
Type: List Polynomial Integer
First compute a decomposition into regular chains (i.e. regular
triangular sets).
lts := triangSolve(lf)$pack
|
|
Type: List RegularChain(Integer,[x,y,z,t])
Then we compute a univariate representation.
|
|
Type:
List Record(
complexRoots: SparseUnivariatePolynomial Integer,
coordinates: List Polynomial Integer)
Note that this computation is made from the input system lf.
However it is possible to reuse a pre-computed regular chain as follows:
|
|
Type: RegularChain(Integer,[x,y,z,t])
|
|
Type: List Record(
complexRoots: SparseUnivariatePolynomial Integer,
coordinates: List Polynomial Integer)
Type: List List RealClosure Fraction Integer
We compute now the full set of points with real coordinates:
lr2 := realSolve(lf)$pack
Type: List List RealClosure Fraction Integer
The number of real solutions for the input system is:
Type: PositiveInteger
Another example of computation of real solutions illustrates the
LexTriangularPackage package constructor.
We concentrate now on the solutions with real (strictly) positive
coordinates:
lpr2 := positiveSolve(lf)$pack
|
|
Type: List List RealClosure Fraction Integer
Finally, we approximate the coordinates of this point with 20 exact digits:
[approximate(r,1/10**21)::Float for r in lpr2.1]
|
|
Type: List Float