This is an introduction to the software developed by the FRISCO project, The main area for which this software was designed is the solution of systems of polynomial equations. More precisely, if F1,..., Fm are polynomials depending on n variables X1,..., Xn with rational coefficients, then we are interested in information about the set of complex or real solutions of the polynomial system:
Two principal methodologies exist: those using Gröbner bases and related techniques, and those using resultants. The first is covered in Section 7.2 (to simplify the presentation we are considering that the pseudodivision procedures used there are like a Gröbner basis computation), 7.3 and 7.5, while Section 7.4 provides several tools to deal with this problem using resultants. Section 7.6 presents a specialised library for the very efficient solution of univariate polynomial equations. In general, and for the case where there are a finite number of complex solutions, first an algebraic computation is performed (a Gröbner basis computation, a triangular decomposition or a resultant-like construction), and finally the solutions are determined and/or presented by using a numerical or semi-numerical method (an eigenvalue computation, an application of Uspensky's or Aberth's method, ...).
This report is aimed at a non-expert user who is unfamiliar with the software, and wishes to assess its suitability for his or her own problems. Thus the description of each piece of software is divided into three sections:
Each description also includes details about how the software can be obtained, either via a soecific URL or by sending email to the responsible FRISCO partner.
If a new user is interested in the algorithms that have been implemented in the different pieces of the FRISCO software described in this report, then the main reference will be `` The FRISCO book on algorithms'', to be published by Springer-Verlag in 2000. In the meantime, the following references (in addition to the documentation accompanying the software) can be used to get more information about the algorithms:
Aldor (A Language for Describing Objects and Relationships) is a high-level programming language designed specifically for symbolic and symbolic/numeric computation. Originally intended as an extension language for the AXIOM computer algebra system it is capable of being used to generate stand-alone applications as well as to embed symbolic code into applications written in C, C++ and Fortran. It is a product of NAG Ltd. In addition, the current compiler can also run as an interpreter allowing interactive experimentation.
The Aldor libraries provide a variety of facilities for basic programming and polynomial solving. There were four libraries produced in the FRISCO project:
BasicMath is built on top of BasicLib, while the other libraries are built on top of BasicMath.
It is anticipated that the Aldor libraries will be released as part of one or more commercial products by NAG. In the meantime it is possible to apply to be a beta tester. Version 1.1.12 of the Aldor compiler is available with AXIOM 2.2.
We will illustrate the basic steps for using the Aldor libraries with a simple example:
#include "basicmath"
import from Symbol, NonNegativeInteger, Integer,
SparseUnivariatePolynomial(Integer,+"x");
-- Create the polynomials
p1 := (term(5,+3) - 7)^(+2) - 4;
p2 := term(3,+2) - 3;
print << "The GCD of (" << p1 << "," << p2 << ") is:" << newline;
print << gcd(p1,p2) << newline;
Line 1 includes a file of definitions to allow the BasicMath (and consequently BasicLib) libraries to be used in the program. Lines 3 and 4 bring the exported symbols of a number of Aldor types into scope in the usual way. We note that the + operator is used to create a literal Symbol in line 4 and literal NonNegativeIntegers in lines 7 and 8. The structure of this program will be completely familiar to an Aldor programmer.
This program must be linked against the BasicMath and BasicLib libraries before it can be run. For example, if the file is called ``gcd.as'', a Unix user might compile it with the command:
axiomxl -Fx -Y /aldor/lib -I /aldor/include -lbasicmath -lbasiclib
if the libraries are installed under the directory /aldor. Note
that the order of libraries on the command line is significant: since some
constructors in BasicLib are extended in BasicMath, the
latter must come first (for more details about the Aldor extend
command see The AXIOM Library Compiler User Guide).
The Aldor libraries are collections of components to allow a user to implement their own application. Some examples are provided in the apps directory, in particular there is a program ( gbtest) for computing gröbner bases in the gb directory. The set of polynomials is first stored in a file, for example the well-known Katsura 5 example is input as:
x y z t u v;
2*x^2 + 2*y^2 + 2*z^2 + 2*t^2 + 2*u^2 + v^2 - u;
2*x*y + 2*y*z + 2*z*t + 2*t*u + 2*u*v - u;
2*x*z + 2*y*t + 2*z*u + u^2 + 2*t*v - t;
2*x*t + 2*y*u + 2*t*u + 2*z*v - z;
t^2 + 2*x*v + 2*y*v + 2*z*v -y;
2*x + 2*y + 2*z + 2*t + 2*u + v - 1;
(where the first line is the list of variables). A number of well known
examples are provided in the distribution.
The syntax for running the program is:
gbtest <filename> <ordering>
where <ordering> is one of lex (lexicographic), deglex
(total degree followed by lexicographic), degrevlex (total degree
followed by reverse lexicographic) , silex, sideglex
or sidegrevlex (as before but using SingleInteger rather
than arbitray precision exponents), and elim-N-* (elimination
ordering).
In the apps/gbrs directory there is a demo of the use of the IdealSolve library which calls the RealSolving program described in section 7.3.
A simple example of the use of the RadicalSolve library is the following.
#include "basicmath"
RegularSetSolvePackage: with {
main: ()->();
++ `main()' is the top level procedure. It reads the command line, gets the
++ options and launches the appropriate computations.
ReadAndSolve: (File, RadicalSolveCommandLine) -> ();
++ `ReadAndSolve(f,cl)' reads the polynomial system from `f', and solves it
++ according to the options of `cl' assuming that the coefficients are in Z.
} == add {
import from String, TextWriter, List Symbol, RadicalSolveCommandLine,
RadicalSolveMessage, AlgebraicEquationsReader, OperatingSystemInterface;
main():() == {
--% GET the command line %--
rdscl: RadicalSolveCommandLine := getCommandLine();
--% CHECK everything is well defined %--
pfn: Partial(FileName) := getInputFile(rdscl);
failed? pfn => print << RDS__error__no__input__file << newline;
fn := retract(pfn)@FileName;
pf: Partial(File) := assignIfCan(fn);
failed? pf => print << RDS__error__input__file__not__present << newline;
f: File == retract(pf);
--% READ and SOLVE the input system %--
ReadAndSolve(f,rdscl);
}
ReadAndSolve(f: File, rdscl: RadicalSolveCommandLine): () == {
--% READ the polynomials %--
(lv: List Symbol, ps) == getIntegerPolynomials(f)$AlgebraicEquationsReader;
import from PolynomialSet(Integer,lv);
if printInput?(rdscl) then print << ps << newline << newline;
--% SOLVE the polynomial system %--
import from RegularTriangularSet(Integer,lv);
for cs in zeroSetSplit(ps,rdscl) repeat print << cs << newline << newline;
}
}
import from RegularSetSolvePackage;
main();
It reads a set of polynomials from a file
and computes their triangular decomposition subject to various command
line options. For example if the file neural.rds contains the
polynomial system:
x y z a;
x^2*z+y^2*z-z*a+1;
x^2*y+y*z^2-y*a+1;
x*y^2+x*z^2-x*a+1;
then the result of running the command:
regsetsolve neural.rds
would be:
{2*z^7 -5*a*z^5 -z^4 +4*a^2*z^3 +2*a*z^2 +(-a^3 -1)*z -a^2,
(8*a*z^6 +(-2*a^3 -20)*z^5 -18*a^2*z^4 +(4*a^4 +28*a)*z^3 +(12*a^3 -4)*z^2
+(-2*a^5 -6*a^2)*z -2*a^4)*y^2 +(-8*z^6 +4*a^2*z^5 +20*a*z^4 +(-8*a^3 -16)*z^3
-16*a^2*z^2 +(4*a^4 +4*a)*z +4*a^3)*y -6*a^2*z^6 +(a^4 +2*a)*z^5 +(13*a^3 -14)*
z^4 +(-2*a^5 -2*a^2)*z^3 +(-8*a^4 +28*a)*z^2 +(a^6 -a^3 -10)*z +a^5 -10*a^2,
(y^2 +z^2 -a)*x +1}
{4*a*z^7 -4*z^6 -4*a^2*z^5 +(a^3 -4)*z^3 +a^2*z^2 -a*z -1,
(6*a*z^7 -6*z^6 -7*a^2*z^5 +2*a*z^4 +(2*a^3 +1)*z^3 +a^2*z^2 -2*a*z -1)*y
+4*a*z^5 -4*z^4 -3*a^2*z^3 +2*a*z^2 +z,
(y^2 +z^2 -a)*x +1}
{2*a^9 -135*a^6 +1566*a^3 -1458,
(740492101*a^7 -10694961294*a^4 +10135304334*a)*z -4800173617*a^6
+69864904278*a^3 -66220529238,
z*y^3 +(-z^3 +1)*y -z,
(y^2 +z^2 -a)*x +1}
The principal documentation for the Aldor language is The AXIOM Library Compiler User Guide by Watt et al, published by NAG Ltd. An updated online version is included as part of the AXIOM 2.2 distribution.
The libraries themselves come with the BasicMath Library User Guide (in the doc directory) which gives an overview of the structure of the libraries, along with some descriptions of the top level domains. There is also a program (in the apps/browser firectory) which will automatically extract all the documentation and descriptions from the library and create a comprehensive LaTeX document (currently around 1200 pages). The document is designed to be used with a recent version of xdvi which supports hyperlinks, or to be turned into a pdf document using the pdflatex program.
In addition, the source tree for the libraries includes a test suite which can be run automatically using the testaxl program supplied. These may also serve as examples of how the various constructors in the libraries should be used.
Gb and RealSolving are very efficient tools for polynomial system solving. Gb, developed by J.-C. Faugere, specialises in very efficient Gröbner bases computations. RealSolving, developed by F. Rouillier, is designed to find, in a very efficient way, information about the real solutions of zero-dimensional polynomial systems.
Both systems have recently evolved (from both the algorithmic and the implementation points of view) into more efficient tools called FGb and RS.
The easiest way to use Gb and RealSolving is through their interface to the Computer Algebra System MuPAD (free licenses are available for some non-commercial categories of users).
The MuPAD modules required in order to use Gb and RealSolving under Linux or Solaris can be obtained from here. The instructions given here are for Linux.
After unzipping and untarring the file GBRSOLVE.linux.tar.gz the directory GBRSOLVE is obtained with the following contents:
gvega@brutus:/home/gvega/GBRSOLVE > ls
doc modules_i386_glibc1 modules_i386_libc5
i386 modules_i386_glibc2.0 modules_i386_libc6
i686 modules_i386_glibc2.1
For a first user the most important directory is the one called doc which contains:
gvega@brutus:/home/gvega/GBRSOLVE/doc > ls
COPYING mupdoc.ps robot_xmupad
EXAMPLES mupload simple
In order to start, first the mupload file must be edited:
gvega@brutus:/home/gvega/GBRSOLVE/doc > more mupload
# name of the machine where to run Gb #
gb_machine:="":
# location of the Gb Servers on the target machine #
GbHome:="";
arch:=sysname(Arch):
.....................................................
and the line where the variable GbHome is defined must be modified
to point to the location of the directory GBRSOLVE:
gvega@brutus:/home/gvega/GBRSOLVE/doc > more mupload
# name of the machine where to run Gb #
gb_machine:="":
# location of the Gb Servers on the target machine #
GbHome:="/home/gvega/GBRSOLVE/";
arch:=sysname(Arch):
.....................................................
Before starting the computation of a first example (see next section), the mupad modules for Gb and RealSolving must be copied into the working directory: in our case the one called doc inside GBRSOLVE. In the Linux case this is made by copying the content of the directory modules_i386_libc5 into the doc directory:
gvega@brutus:/home/gvega/GBRSOLVE > cp modules_i386_libc5/* doc/
gvega@brutus:/home/gvega/GBRSOLVE > ls doc
COPYING gb.mdm mupload robot_xmupad rsu.mdm
EXAMPLES mupdoc.ps newrs.mdm rs.mdm simple
In the Solaris case the directory modules_i386_libc5 must be replaced by
the modules_solaris directory also present in GBRSOLVE.
The first example to try is contained in the file simple (in the doc directory) where the polynomial system
# This simple example shows how to use Gb/RealSolving for
isolating with intervals with rational bounds all the coordinates
of the solutions of a given polynomial system #
read("mupload");
#the system #
vars:=[x,y,z,t,u,v];
F1:=2*x^2+2*y^2+2*z^2+2*t^2+2*u^2+v^2-v;
F2:=2*x*y+2*y*z+2*z*t+2*t*u+2*u*v-u;
F3:=2*x*z+2*y*t+2*z*u+u^2+2*t*v-t;
F4:=2*x*t+2*y*u+2*t*u+2*z*v-z;
F5:=t^2+2*x*v+2*y*v+2*z*v-y;
F6:=2*x+2*y+2*z+2*t+2*u+v-1;
l0:=[F1,F2,F3,F4,F5,F6];
#compute a groebner basis #
base:=gbgb(l0,vars):
#compute a rational univariate representation #
rur:=rsrur(base):
#isolate the roots of the first polynomial of the RUR
with intervals of lenght 1/10^8 #
rac:=isoleusp(op(rur,1),10^8):
#number of realroots of the system #
nops(rac);
..................................................................
Next we show the start of the computation with MuPAD plus the
display of the degree 32 polynomial mentioned in the previous section
and the fact that the number of real solutions of the polynomial system
is 12.
gvega@brutus:/home/gvega/GBRSOLVE/doc > mupad
*----* MuPAD 1.4.1 -- Multi Processing Algebra Data Tool
/| /|
*----* | Copyright (c) 1997 - 98 by SciFace Software GmbH
| *--|-* All rights reserved.
|/ |/
*----* Licensed to: Laureano Gonzalez-Vega
>> read("simple");
"/home/gvega/GBRSOLVE/"
"/home/gvega/GBRSOLVE/i386"
..............................................................
>> op(rur,1);
32
poly(400734076818507298790915386114048 x +
31
(-1016509441504700588061778383994880) x +
30
960525833602408454309198241464320 x +
..............................................................
>> nops(rac);
12
Another very interesting example (which requires the using of xmupad instead of mupad) is contained in the file robot_xmupad (found also in the directory GBRSOLVE/doc) where, given a base (A1,..., A6) and a Stewart platform located at (B1,..., B6) with lengths (l1,..., l6), the possible positions for the platform such that AiBi = li are computed and drawn.
The postscript file mupdoc.ps can be found in the doc directory and it contains a very clear user guide about how to use Gb and RealSolving through the MuPAD interface.
The book Dynamic Modules by A. Sorgatz (Springer-Verlag, 1999) is very useful in order to understand how modules work under MuPAD and the accompanying CD-ROM also contains the Gb and RealSolving modules described here.
It is also posible to use Gb and RealSolving as stand alone applications or access RealSolving from the PoSSoServer (see section 7.5.3).
ALP (Algèbre Linéaire pour les Polynomes) is a C++ class library for computations involving linear and polynomial algebra. It contains classes for vectors, matrices, monomials and polynomials and algorithms for solving equations. It can also be connected to several external and specialised libraries such as gmp, umfpack, Lapack, RS (see Section 7.3) and MPSolve (see Section 7.6).
From this site, download the latest version of the file alp.tgz. Alternatively you can download the version of the library plus the documentation produced in the FRISCO project. After that, the unix command ``gzip -dc alp.tgz |tar -xvf -'' produces a directory alp containing the source directory, the include directory and directories of external compiled libraries:
gvega@brutus:/home/gvega > ls alp
alp0.98 include lib-linux
The README file at the directory alp0.98
gvega@brutus:/home/gvega/alp/alp0.98 > ls
COPYRIGHT Config EXPL Makefile README SRC manual.ps.gz
contains the instructions required to start working with ALP. First
the unix command make must be executed in the Config directory
gvega@brutus:/home/gvega/alp/alp0.98/Config > make
echo ""#!/usr/local/bin/perl"" > alp
echo "\$DIR=\"\";" | sed -e "s/Config//g">> alp
echo "\$system="\`system\`";">> alp
cat alp.config >> alp
chmod u+x alp
providing a perl script whose first lines are shown:
gvega@brutus:/home/gvega/alp/alp0.98/Config > more alp
#!/usr/local/bin/perl
$DIR="";
$system=`system`;
$system=~s/\n//g;
if(@ARGV[0] eq "?"){
$name=@ARGV[1];
$name=~s/</\\</g;
.......................................................
As already described in the README file, now at the Config directory,
the first three lines of the perl script must be changed
in order to tell ALP where perl is, where the alp0.98
directory is located, and which is the operating system being used.
gvega@brutus:/home/gvega/alp/alp0.98/Config > more alp
#!/usr/bin/perl
$DIR="/home/gvega/alp/alp0.98";
$system=linux;
$system=~s/\n//g;
if(@ARGV[0] eq "?"){
$name=@ARGV[1];
$name=~s/</\\</g;
.......................................................
The final step before starting to use ALP is to tell it where the
C++ compiler is if /usr/local/bin/ is not the right
directory. Not all the compilers implement the required ISO/ANSI C++
standard to compile ALP. The current version has been tested
with a version of egcs greater than egcs.2.90 under the operating
systems Solaris 2.6 and Linux. For the Linux machine considered
in this section it was required to modify the CC variable in
the Makefile.default in
the Config directory in order to tell ALP where the compiler
was located:
gvega@brutus:/home/gvega/alp/alp0.98/Config > more Makefile.default
# = Commandes ===============================================
CC=/huge/soft/egcs-1.1.2/bin/g++
...........................................................................
Finally, in our case (the compiler not located in the usual place)
it was also necessary to modify
the .bashrc file in order to tell ALP where the
/huge/soft/egcs-1.1.2/lib/ directory is.
ALP is designed to compile C++ files containing the description of the problem to be solved. This file:
gvega@brutus:/home/gvega > more example1.cc
#include "_MPoly.H"
#include "_Matrix.H"
#include "algo/Macaulay.H"
#define Mon Monom<double,dynamicexp<'x'> >
#define Pol MPoly<list<Mon>, Dlex<Mon> >
#define Mat MatStd<array2d<double> >
int main (int argc, char **argv)
{
VectStd<array1d<Pol> > L(3);
L[0] = Pol("x1+x2+1;");
L[1] = Pol("2*x1^2+2*x2^2+2;");
L[2] = Pol("3*x1^2+3*x1*x2+3;");
cout<<L<<endl;
cout<<Macaulay(L,array2d<double>())<<endl;
};
contains the definition of three polynomials together with the
instructions required
to compute the Macaulay matrix whose determinant is a multiple of the
resultant of the three polynomials.
Once the (.cc) file has been edited the perl script ALP generates an
executable (.ex) file:
gvega@brutus:/home/gvega > alp example1.cc
>> make ALP_DIR=/home/gvega/alp/alp0.98
-f /home/gvega/alp/alp0.98/Config/Makefile.linux example1.ex
----------------------------------
/huge/soft/egcs-1.1.2/bin/g++ -Wall -O6 -I/home/gvega/alp/alp0.98/SRC -I/home
/gvega/alp/alp0.98/SRC/arithm -I/home/gvega/alp/include -I/0/saga/mou
rrain/C++/alp1.0/include/ -L/home/gvega/alp/lib-linux -o example1.ex
example1.cc -ltoric -lincres -lmps -lgmp -llapack -lblas -lf2c -lm -lalp
----------------------------------
Finally running the example1.ex file, the desired result is obtained
gvega@brutus:/home/gvega > example1.ex
[(1)+(1)*x1+(1)*x2, (2)+(2)*x1^2+(2)*x2^2, (3)+(3)*x1^2+(3)*x1*x2]
Passe.......4
Passe.......5
[ 1 0 0 0 2 0 0 3 0 0 ]
[ 1 1 0 0 0 2 0 0 3 0 ]
[ 1 0 1 0 0 0 2 0 0 3 ]
[ 0 1 1 1 0 0 0 3 0 0 ]
[ 0 1 0 0 2 0 0 3 0 0 ]
[ 0 0 0 0 0 2 0 0 3 0 ]
[ 0 0 0 1 0 0 2 0 3 3 ]
[ 0 0 1 0 2 0 0 0 0 0 ]
[ 0 0 0 1 0 2 0 0 0 3 ]
[ 0 0 0 0 0 0 2 0 0 0 ]
The next example,
gvega@brutus:/home/gvega > more example2.cc
#include "_MPoly.H"
#include "_Matrix.H"
#include "algo/Toric.H"
#define Mon Monom<double,dynamicexp<'x'> >
#define Pol MPoly<list<Mon>, Dlex<Mon> >
#define Mat MatStd<array2d<double> >
int main (int argc, char **argv)
{
list<Pol> L;
Pol p1("x1^3-x1*x2+x2-1;"); L.push_back(p1);
Pol p2("x1^4+x1*x2^3-x2+1;");L.push_back(p2);
cout<<MixedVolume(L,L.size())<<endl;
};
shows how to use from ALP the C-implementation of I. Emiris for
computing the mixed volume, providing
a Bezout-like bound for the number of complex roots of a polynomial
system of equations.
gvega@brutus:/home/gvega > example2.ex
Mixed Volume program wrote mixed cells in: ToricMVOutput.cell.
10
In this particular case, apart from the mixed volume, more
information about how the computation
was performed can be found in the file ToricMVOutput.cell.
gvega@brutus:/home/gvega > more ToricMVOutput.cell
Seed = 1.
1-th lifting vector: [ 599836 168513 ]
2-th lifting vector: [ 699977 394218 ]
Took -17895733 minutes for hull vertices, edges
These are the mixed cells of the Minkowski Sum.
each cell = sum of edges with indices in <...>.
Edge of polytope 1 polytope 2.
Heads [ 0 1 168513 ] [ 0 0 0 ]
Tails [ 1 1 768349 ] [ 0 1 394218 ]
< 2 0 > Cell volume = 1.
Heads [ 0 1 168513 ] [ 0 1 394218 ]
Tails [ 1 1 768349 ] [ 1 3 1882631 ]
< 2 2 > Cell volume = 2.
Heads [ 1 1 768349 ] [ 0 0 0 ]
Tails [ 3 0 1799508 ] [ 4 0 2799908 ]
< 3 1 > Cell volume = 4.
Heads [ 1 1 768349 ] [ 4 0 2799908 ]
Tails [ 3 0 1799508 ] [ 1 3 1882631 ]
< 3 3 > Cell volume = 3.
Total number of mixed cells = 4
Total mv = 10. Total time = -298262h -13m -16s.
The last two examples show how ALP can be used to solve polynomial systems of equations in the absence of singular solutions. For that it is required to have a presentation of the quotient algebra plus the matrix of multiplication by one element (usually one of the variables). The file corresponding to the first example, extracted from chapter 20 of the ALP manual, is the following one:
gvega@brutus:/home/gvega > more example3.cc
#include "_Lapack.H"
#include "algo/SolveEigen.H"
#define VCT VectStd<array1d<double> >
#define MAT MatSpl<lapack<double> >
#define MATC MatSpl<lapack<complex<double> > >
int main (int argc, char **argv) {
double v[]={0,1,0,0, 1,1,0,-2, 0,0,0,1, -2.8,-2.4,0.2,5.8};
MAT A(4,4,v);
cout<<A<<endl;
cout<<Eigenvct(A)<<endl;
cout<<Solve(A,2,Eigen())<<endl;
};
The polynomial system to be solved is
[x1, x2]/(f1, f2) is
{1, x1, x2, x1x2}.
The cc file contains the definition of the matrix A (which is
the transpose of the multiplication matrix times
x1 with respect to the considered basis) written in vector form
and then the computation of the eigenvectors of this matrix.
Finally, the solutions are recovered from these eigenvectors:
gvega@brutus:/home/gvega > example3.ex
[ 0 1 0 -2.8 ]
[ 1 1 0 -2.4 ]
[ 0 0 0 0.2 ]
[ 0 -2 1 5.8 ]
[ (0.397213,0) (-0.157827,0) (-0.283951,0.267255) (-0.283951,-0.267255) ]
[ (0.40724,0) (-0.922776,0) (0.842467,0) (0.842467,-0) ]
[ (-0.0241072,0) (-0.167928,0) (-0.126108,-0.173973) (-0.126108,0.173973) ]
[ (-0.822068,0) (-0.30883,0) (0.300799,0.0393228) (0.300799,-0.0393228) ]
[ (6.8201,0) (0.367814,-0) (-0.193954,-0.205207) (-0.193954,0.205207) ]
[ (-2.83673,0) (1.67548,-0) (-0.619371,1.38952) (-0.619371,-1.38952) ]
The last two lines contains the solutions: the list at the
11-th line provides the x1-coordinates of the solutions,
the list at the 12-th line the x2-coordinates of the solutions
and they are suitably ordered. The four solutions
{
: 1 
i 4} are for this example:
The last example is a little bit more complicated. The polynomial system to solve is:
[x, y, z]/(f1, f2, f3) (the dimension of
this vector space is 87):
gvega@brutus:/home/gvega > more example4.cc
#include "_Lapack.H"
#include "algo/SolveEigen.H"
#define VCT VectStd<array1d<double> >
#define MAT MatSpl<lapack<double> >
#define MATC MatSpl<lapack<complex<double> > >
int main (int argc, char **argv) {
double v[]={0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ......
....................................................................
0, 0, 0, 0, -.379575, -.526660, -.126622, -.275287, 1.35156,
-.114737,-2.01241, 2.07403, -.353449, -1.21954, .672595,
-.188956,-.327586, -1.30784, .244081, .443618, -.870331, .....
....................................................................
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1., 0 };
MAT A(87,87,v);
cout<<Solve(A,3,Eigen())<<endl;
};
Finally the 87 solutions were obtained by ALP:
gvega@brutus:/home/gvega > example4.ex
[ (-0.920231,-1.22005) (-0.920231,1.22005) (-0.958092,-1.18116) (-0.958092,1.181
16) (-1.23922,-0.913405) (-1.23922,0.913405) (-0.555295,-1.40711) (-0.555295,1.4
0711) (-0.561921,-1.40601) (-0.561921,1.40601) (-1.44486,-0.475932) (-1.44486,0.
475932) (-1.21465,-0.773789) (-1.21465,0.773789) (-1.47654,-0.00986409) (-1.4765
4,0.00986409) (-1.378,-0.369451) (-1.378,0.369451) (-0.930208,-0.913286) (-0.930
208,0.913286) (-0.125916,-1.53037) (-0.125916,1.53037) (-0.0727661,-1.471) (-0.0
727661,1.471) (-1.30337,-0.059009) (-1.30337,0.059009) (-1.10011,-0.618848) (-1.
10011,0.618848) (-0.998298,-0.580466) (-0.998298,0.580466) (-1.07024,-0.205689)
(-1.07024,0.205689) (-1.07718,-0.121943) (-1.07718,0.121943) (0.34119,-1.51178)
(0.34119,1.51178) (0.299383,-1.44371) (0.299383,1.44371) (-0.905457,-0.150304) (
-0.905457,0.150304) (-0.132861,-1.07703) (-0.132861,1.07703) (-0.574314,-0.21336
8) (-0.574314,0.213368) (0.687521,-1.32419) (0.687521,1.32419) (0.753747,-1.3007
) (0.753747,1.3007) (-0.0660515,-0.835593) (-0.0660515,0.835593) (1.10496,-1.021
38) (1.10496,1.02138) (1.08457,-0.994771) (1.08457,0.994771) (0.173584,-0.90088)
(0.173584,0.90088) (1.33805,-0.682414) (1.33805,0.682414) (1.36516,-0.631753) (
1.36516,0.631753) (1.49898,-0.246804) (1.49898,0.246804) (0.677186,-0.960222) (0
.677186,0.960222) (1.4345,-0.192487) (1.4345,0.192487) (0.608181,-0.910542) (0.6
08181,0.910542) (0.700579,-0.895614) (0.700579,0.895614) (0.00689092,-0.538493)
(0.00689092,0.538493) (1.13519,-0.517383) (1.13519,0.517383) (0.812631,-0.588649
) (0.812631,0.588649) (0.856486,-0.491165) (0.856486,0.491165) (0.882818,-0.3633
36) (0.882818,0.363336) (0.666262,-0.321071) (0.666262,0.321071) (0.831097,0) (0
.79978,-0.139269) (0.79978,0.139269) (0.676612,-0.160178) (0.676612,0.160178) ]
[ (1.76682,-1.67553) (1.76682,1.67553) (1.37462,-1.8323) (1.37462,1.8323) (-1.92
677,-1.50763) (-1.92677,1.50763) (1.45019,1.64931) (1.45019,-1.64931) (1.48823,1
.75398) (1.48823,-1.75398) (-0.769101,2.1215) (-0.769101,-2.1215) (-1.54971,-0.5
23606) (-1.54971,0.523606) (1.9722,0.152248) (1.9722,-0.152248) (-0.0160939,1.71
332) (-0.0160939,-1.71332) (-0.742208,-0.0581691) (-0.742208,0.0581691) (-2.1599
8,1.0796) (-2.15998,-1.0796) (-1.83281,0.585427) (-1.83281,-0.585427) (-0.608617
,-0.673615) (-0.608617,0.673615) (-0.956275,0.380686) (-0.956275,-0.380686) (-0.
499853,-0.709838) (-0.499853,0.709838) (0.3666,0.673432) (0.3666,-0.673432) (0.6
73032,-0.468903) (0.673032,0.468903) (-0.622319,-2.49002) (-0.622319,2.49002) (-
0.639471,-1.93156) (-0.639471,1.93156) (0.696461,-0.10034) (0.696461,0.10034) (-
0.402821,0.891604) (-0.402821,-0.891604) (-0.0662398,0.790554) (-0.0662398,-0.79
0554) (1.96787,-0.521265) (1.96787,0.521265) (2.14791,-0.0767035) (2.14791,0.076
7035) (-0.191488,0.847992) (-0.191488,-0.847992) (-0.543185,2.03772) (-0.543185,
-2.03772) (-0.518669,1.91603) (-0.518669,-1.91603) (-0.303359,0.740136) (-0.3033
59,-0.740136) (-2.05654,-0.735648) (-2.05654,0.735648) (-1.87683,-1.04482) (-1.8
7683,1.04482) (1.26357,-1.84939) (1.26357,1.84939) (0.614688,0.62195) (0.614688,
-0.62195) (1.16568,-1.32643) (1.16568,1.32643) (0.629296,0.5961) (0.629296,-0.59
61) (0.744944,0.689993) (0.744944,-0.689993) (-0.716338,-0.0368001) (-0.716338,0
.0368001) (0.585593,-0.287251) (0.585593,0.287251) (0.665893,-0.331104) (0.66589
3,0.331104) (0.732382,-0.276892) (0.732382,0.276892) (-0.0732781,-0.766197) (-0.
0732781,0.766197) (-0.103434,-0.680544) (-0.103434,0.680544) (-0.55105,0) (-0.16
9123,-0.673609) (-0.169123,0.673609) (-0.685934,-0.0142516) (-0.685934,0.0142516
) ]
[ (-1.87765,2.64148) (-1.87765,-2.64148) (1.23768,-2.7684) (1.23768,2.7684) (3.2
499,0.127679) (3.2499,-0.127679) (1.38801,2.53523) (1.38801,-2.53523) (-1.4179,-
2.67807) (-1.4179,2.67807) (-2.00437,-2.15536) (-2.00437,2.15536) (-1.90894,0.66
2592) (-1.90894,-0.662592) (-0.208876,2.49564) (-0.208876,-2.49564) (1.88405,0.8
86332) (1.88405,-0.886332) (-1.05356,0.053485) (-1.05356,-0.053485) (3.14663,0.6
52046) (3.14663,-0.652046) (-2.29335,-0.922774) (-2.29335,0.922774) (0.146333,0.
605574) (0.146333,-0.605574) (0.038845,0.926264) (0.038845,-0.926264) (-1.08817,
-0.18184) (-1.08817,0.18184) (0.44826,-0.579882) (0.44826,0.579882) (-0.608677,-
0.265166) (-0.608677,0.265166) (-2.64541,2.22845) (-2.64541,-2.22845) (1.85919,-
1.86862) (1.85919,1.86862) (0.342026,-0.648777) (0.342026,0.648777) (-0.859065,0
.222999) (-0.859065,-0.222999) (0.480617,0.618703) (0.480617,-0.618703) (0.79612
6,2.49487) (0.796126,-2.49487) (-0.125533,-2.78018) (-0.125533,2.78018) (0.26203
,0.514735) (0.26203,-0.514735) (-2.06781,-1.7888) (-2.06781,1.7888) (1.89793,1.6
6648) (1.89793,-1.66648) (0.445547,-0.464797) (0.445547,0.464797) (-2.66284,0.97
7785) (-2.66284,-0.977785) (2.75882,-0.429981) (2.75882,0.429981) (1.03058,-2.74
158) (1.03058,2.74158) (-0.156083,-0.0785868) (-0.156083,0.0785868) (-1.07049,1.
94131) (-1.07049,-1.94131) (0.615627,-0.429566) (0.615627,0.429566) (-0.663794,0
.565996) (-0.663794,-0.565996) (0.437496,-0.610565) (0.437496,0.610565) (-0.2879
87,0.789171) (-0.287987,-0.789171) (0.481432,-0.320732) (0.481432,0.320732) (-0.
304055,-0.3989) (-0.304055,0.3989) (0.163212,0.693616) (0.163212,-0.693616) (0.4
85191,-0.357216) (0.485191,0.357216) (-0.615938,0) (-0.550406,-0.295876) (-0.550
406,0.295876) (0.277791,0.526421) (0.277791,-0.526421) ]
Note that only one of the solutions (line 22 for x, 45 for
y and 69 for z) of the polynomial system under consideration is
real:
The ALP web page contains more information, along with an html version of the manual.
The PoSSo Library is a C++ library whose development started in the ESPRIT/BRA project PoSSo (Polynomial System Solving) under the direction of Carlo Traverso, and which has been greatly extended and improved inside the LTR project FRISCO.
The main purpose of the PoSSo Library (which we shall refer to as ``PoSSoLib'' in what follows) is to provide tools to deal with polynomial system solving through very efficient Gröbner basis computations.
gvega@brutus:/home/gvega/ultpruebas/PoSSoLib-2.1.10 > ls
3rdParty Packages.h install.sh
ChangeLog README installed
FileList README.win32 lib
LICENCE config.guess pippo
Makefile.in config.sub programs
Makefile.include.in configure rcsdirs
Makefile.macros configure.in release
Makefile.target dirtree.txt snapshots
OpenProblems doc tools
By following the steps in the README file, the command configure will
determine the architecture of the computer together with the code that
has to be compiled:
gvega@brutus:/home/gvega/PoSSoLib-2.1.10 > configure
- You did not tell me what kind of host system you want to configure.
- I will attempt to guess the kind of system this is.
- Looks like this is a i586-unknown-linux
Checking the configuration name
checking for ln -s
checking how to run the C preprocessor
checking for a BSD compatible install
checking for ranlib
Using Cmm garbage collection,
Compiling with generic polynomials.
Compiling with generic coefficients (allow run-time switching).
Using GMP BigNums.
Selecting Realsolving.
creating config.status
creating Makefile
creating Makefile.include
updating Makefile.include
updating Makefile
Generating plconfig.h
Finally the make command (taking some time) ends the installation
procedure and the contents of the PoSSoLib-2.1.10
directory are:
gvega@brutus:/home/gvega/ultpruebas/PoSSoLib-2.1.10 > ls
3rdParty Packages.h installed
ChangeLog README lib
FileList README.win32 pippo
LICENCE config.guess plconfig.h
Makefile config.status programs
Makefile.in config.sub rcsdirs
Makefile.include configure release
Makefile.include.in configure.in snapshots
Makefile.macros dirtree.txt tools
Makefile.target doc
OpenProblems install.sh
The main directories, for a first user, are doc and programs. The
first one, containing the documentation, will be considered in
section 7.5.3 and the second one contains the two exec files
providing two ways in which the PoSSoLib can be used:
the SampleSolver (at the programs/Solver directory) and the
PoSSoServer (at the programs/Server directory). These two ways of
using the PoSSoLib are described in detail in the next section.
{4,
{N,{x,y,z,t}},
{L,{1,1,1,1}}
}
{
{1y2z,2xyt,-2x,-1z}
,
{-1x3z,4xy2z,4x2yt,2y3t,4x2,-10y2,4xz,-10yt,2}
,
{2yzt,1xt2,-1x,-2z}
,
{-1xz3,4yz2t,4xzt2,2yt3,4xz,4z2,-10yt,-10t2,2}
}
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// Output from AlPi
// (insert copyright, POSSO, etc.)
//
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
starts by the number of variables (line 2) followed by the definition
of the lexicographical ordering
with x > y > z > t (lines 3 and 4). Then the four polynomials are
introduced monomial by monomial (lines 7, 9, 11 and 13).
Another different example appears in the file cyclic5.in:
{
5,
{C, {1, 1, 1, 1, 1}},
{V, {1, 1, 1, 1, 1}}
}
{{1x,1y,1z,1t,1u},
{1xy,1yz,1zt,1tu,1ux},
{1xyz,1yzt,1ztu,1tux,1uxy},
{1xyzt,1yztu,1ztux,1tuxy,1uxyz},
{1xyztu,-1}}
where the defined ordering is the usual DegRevLex. Note that in this
case the variable names are not specified and therefore
x, y, z, t, u, v, w, a, ..., s are taken as
defaults. The different ways of defining orderings (monoid
specifications in the PoSSoLib terminology) are described in
section 4.2 of the PoSSo Library Reference Manual.
Next the SampleSolver is used in order to compute the Gröbner basis, with respect to the lexicographical ordering with x > y > z > t of the polynomial system in the file caprasse-LEX.in.
gvega@brutus: SampleSolver -V 4 caprasse-LEX.in
2.1.10
...A Posso Product...
Using PDensePP implementation.
Using Coeff Run Time Selection,
with GCoeff implementation.
Using CMM, TempHeap.
Computing the Groebner Basis for:
Input -> { 2*x*y*t-2*x+y^2*z-z
, -(x^3*z-4*x^2*y*t-4*x^2-4*x*y^2*z-4*x*z-2*y^3*t+10*y^2+10*y*t-2)
, x*t^2-x+2*y*z*t-2*z
, -(x*z^3-4*x*z*t^2-4*x*z-4*y*z^2*t-2*y*t^3+10*y*t-4*z^2+10*t^2-2)
}
Sorted Input -> { 2*x*y*t-2*x+y^2*z-z
, -(x^3*z-4*x^2*y*t-4*x^2-4*x*y^2*z-4*x*z-2*y^3*t+10*y^2+10*y*t-2)
, x*t^2-x+2*y*z*t-2*z
, -(x*z^3-4*x*z*t^2-4*x*z-4*y*z^2*t-2*y*t^3+10*y*t-4*z^2+10*t^2-2)
}
Reduced (but not fully reduced) basis: {-(580608*x+1429632*y*z*t+1191*z^7*t^4-26156
*z^7*t^2+18917*z^7-3573*z^5*t^6+12360*z^5*t^4+355641*z^5*t^2-279756*z^5+3573*z
^3*t^8+96624*z^3*t^6+922818*z^3*t^4+284232*z^3*t^2-1210479*z^3-1191*z*t^10-828
28*z*t^8+63082*z*t^6-310272*z*t^4-883051*z*t^2-989516*z)
, -(97284096*y-760032*z^8*t+12160512*z^6*t+19460556*z^4*t^7+38204620*z^4*t^5-12
473244*z^4*t^3-45191932*z^4*t+16023339*z^2*t^11+154231065*z^2*t^9+339820366*z^2*t^
7+72809170*z^2*t^5-456015817*z^2*t^3-321436315*z^2*t-12913760*t^9+108870080*t^7
+198621696*t^5-108870080*t^3-88423840*t)
, -(27*z*t^14+243*z*t^12+711*z*t^10+559*z*t^8-559*z*t^6-711*z*t^4-243*z*t^2 -
27*z)
, -(76160*z^4*t^2-76160*z^4-35343*z^2*t^12-276156*z^2*t^10-773043*z^2*t^8-65592
0*z^2*t^6+969723*z^2*t^4+873836*z^2*t^2-103097*z^2+19008*t^12-103872*t^10-7897
60*t^8-533120*t^6+843072*t^4+636992*t^2-72320)
, -(24*z^9-384*z^7+1664*z^3*t^4+1792*z^3*t^2+2688*z^3-783*z*t^12-6750*z*t^10
-18537*z*t^8-11140*z*t^6+14735*z*t^4+12098*z*t^2+4233*z)
, -(9600*z^2*t^6+22400*z^2*t^4-22400*z^2*t^2-9600*z^2-270*t^18+513*t^16+17190
*t^14+46826*t^12-34270*t^10-186100*t^8-12190*t^6+143174*t^4+29540*t^2-4413)
, -(27*t^20-1719*t^16-8000*t^14-11746*t^12+11746*t^8+8000*t^6+1719*t^4-27)
}
#PPs = 7
Fully reduced basis: { -(27*t^20-1719*t^16-8000*t^14-11746*t^12+11746*t^8+8000*t
^6+1719*t^4-27)
, -(27*z*t^14+243*z*t^12+711*z*t^10+559*z*t^8-559*z*t^6-711*z*t^4-243*z*t^2 -
27*z)
, -(9600*z^2*t^6+22400*z^2*t^4-22400*z^2*t^2-9600*z^2-270*t^18+513*t^16+17190
*t^14+46826*t^12-34270*t^10-186100*t^8-12190*t^6+143174*t^4+29540*t^2-4413)
, -(16000*z^4*t^2-16000*z^4+64000*z^2*t^4-64000*z^2+2943*t^18+297*t^16-187344
*t^14-890936*t^12-1370330*t^10-138430*t^8+1330344*t^6+1063936*t^4+224387*t^2 -
34867)
, -(24*z^9-384*z^7+1664*z^3*t^4+1792*z^3*t^2+2688*z^3-783*z*t^12-6750*z*t^10
-18537*z*t^8-11140*z*t^6+14735*z*t^4+12098*z*t^2+4233*z)
, -(6144000*y-48000*z^8*t+768000*z^6*t-3328000*z^2*t^5-3584000*z^2*t^3-5376000*
z^2*t-627615*t^19-190431*t^17+40085460*t^15+198035588*t^13+321282190*t^11+4866
5150*t^9-311914460*t^7-241936588*t^5-48825575*t^3+1570281*t)
, -(12288*x-128*z^7+1792*z^5-1920*z^3*t^4-1280*z^3*t^2+5248*z^3-2079*z*t^12 -
17334*z*t^10-44865*z*t^8-28980*z*t^6+24591*z*t^4+29642*z*t^2+22641*z)
}
#PPs = 7
Computation summary:
Time: User 0.33 System 0.08 Real 0.56
Memory: 132772 PageFault 7 Host brutus
Pairs: Total 111 Useful 69 Useless 42 Discarded 0
File: caprasse-LEX.in
The answer is labelled ``Fully reduced basis'' in a
format readable by most
computer algebra systems, and a ``Computation summary'' appears at
the end including
some informations about the computation performed. A smaller value to
the option -V will
produce either less readable output or only some information about
the computations performed.
A complete list of options for the SampleSolver can be found at
section 2 of the PoSSo Library User Guide.
The full functionality of the PoSSo Library is available by using the PoSSoServer. First of all, the PoSSoServer is started, on a unix machine named frisco, by running the command
frisco% PoSSoServer -p 5001
2.1.10
...A Posso Product...
Using Coeff Run Time Selection.
Using PDensePP.
Using CMM, Posso Specific Memory Management.
DefaultHeap.
Starting GServer
GServer 3 bound to frisco 5001
and now it waits for the running of the example to be verified.
Interaction with the PoSSoServer is via the XCL
language: the file example.xcl (created ad-hoc for this document)
contains a first example of how to tell the PoSSoServer to solve
a polynomial system of equations:
gvega@brutus: more example.xcl
Nop
% PoSSo Server Test
% CountRoots for cyclic5
@
Clear
@
SetAlgoVerbosity 2
@
PR_Open Z {GCoeff} [a, b, c, d, e] {PDensePP} C:1 V:1;
% open PR(0)
@
PL_Open (0) % open PL(1)
@
PL_Put(1)
a*b*c*d*e-1,
a*b*c*d+a*b*c*e+a*b*d*e+a*c*d*e+b*c*d*e,
a*b*c+a*b*e+a*d*e+b*c*d+c*d*e,
a*b+a*e+b*c+c*d+d*e,
a+b+c+d+e;
@
GR_Open (0) % open GR(2)
@
GR_ComputeBasis (2) (1) % compute the Groebner Basis
@
RST_Open (2) % open RST (3) - compute the multiplication table
@
LUP_Open % open LUP (4)
@
RST_GSL (3) (4) % compute GSL
@
UP_Open % open UP (5)
@
RST_UniPol 1 (3) (5) % compute the univariate polynomial on the first variable
@
UP_Get (5)
@
UP_CountRoots (5) % compute the number of roots (real and complex) of (5)
@
LUP_GetFirst (4) (5) % first polynom of GSL in (5)
@
UP_Get (5)
@
UP_CountRoots (5) % compute the number of roots (real and complex) of (5)
@
RST_CountRoots (3) % compute the number of real and complex roots of the system
@
SC_Open % (6) variable for sign conditions
@
SC_Get (6)
@
PL_Open (0) % open PL (7)
@
PL_Put (7) a,b,c,d,e;
@
RST_SI (3) (7) (6) % Simultaneous inequalities
@
SC_Get (6)
@
Clear
@
Nop
End of RScyclic6.xcl
@
The most important parts of this file are the following commands:
Once the input file is ready, the PoSSoServer running on the frisco machine is told to execute the XCL-commands previously described:
gvega@brutus: runtest -m frisco -p 5001 example.xcl
PoSSo Server Tester. 2.1.10
...A Posso Product...
ok.
***SourceFile: ./tests/example.xcl*
<<Nop
% PoSSo Server Test
% CountRoots for cyclic6
@
>>0, T:0.00@
<<Clear
@
>>0, T:0.00@
<<SetAlgoVerbosity 2
@
>>0, T:0.00@
<<PR_Open Z {GCoeff} [a, b, c, d, e] {PDensePP} C:1 V:1;
% open PR(0)
@
>>0,(0) T:0.00@
<<PL_Open (0) % open PL(1)
@
>>0,(1) T:0.00@
<<PL_Put(1)
a*b*c*d*e-1,
a*b*c*d+a*b*c*e+a*b*d*e+a*c*d*e+b*c*d*e,
a*b*c+a*b*e+a*d*e+b*c*d+c*d*e,
a*b+a*e+b*c+c*d+d*e,
a+b+c+d+e;
@
>>0, T:0.00@
<<GR_Open (0) % open GR(2)
@
>>0,(2) T:0.00@
<<GR_ComputeBasis (2) (1) % compute the Groebner Basis
@
>>0, T:0.27@
<<RST_Open (2) % open RST (3) - compute the multiplication table
@
>>0,(3) T:4.41@
<<LUP_Open % open LUP (4)
@
>>0,(4) T:0.00@
<<RST_GSL (3) (4) % compute GSL
@
>>0, T:5.41@
<<UP_Open % open UP (5)
@
>>0,(5) T:0.00@
<<RST_UniPol 1 (3) (5) % compute the univariate polynomial on the first variable
@
>>0, T:0.58@
<<UP_Get (5)
@
>>0,{ 70 1 , 65 236 , 60 12716 , 55 -140114 , 50 649126 , 45 -1753252 , 40 3086253 , 35 -3
709932 , 30 3086253 , 25 -1753252 , 20 649126 , 15 -140114 , 10 12716 , 5 236 , 0 1 } T:0
.00@
<<UP_CountRoots (5) % compute the number of roots (real and complex) of (5)
@
>>0,{3,15} T:0.13@
<<LUP_GetFirst (4) (5) % first polynom of GSL in (5)
@
>>0, T:0.00@
<<UP_Get (5)
@
>>0,{ 70 1 , 65 84372086 , 60 238410108238666 , 55 -16216157493424836618314 , 50 343719688
05091489649450178776 , 45 248747625670366906220858383250231998 , 40 -250792140198089733156
345777614436219065947 , 35 -534780284268847660910257211610244214497653885332 , 30 -1223362
16236636512914865827705777586843394729185855847 , 25 2732362019508779025376603916671960400
95894717932475845897698 , 20 -450522616063854592978687742018022551911451078096817171551079
61124 , 15 5838170350592172431421779705365382446614942191776467765289046151821486 , 10 -46
9981907705675737840264277167090736130947468692277503649090655310905628 34, 5 8398220136645
0233228895209695988695424448539944411106870905949856570426101786, 0 551029233460140804097
29485561260334382506146604497562445733202402991488777106901 } T:0.00@
<<UP_CountRoots (5) % compute the number of roots (real and complex) of (5)
@
>>0,{10,70} T:6.85@
<<RST_CountRoots (3) % compute the number of real and complex roots of the system @
>>0,{10,70} T:1.98@
<<SC_Open % (6) variable for sign conditions
@
>>0,(6) T:0.00@
<<SC_Get (6)
@
>>0,} T:0.00@
<<PL_Open (0) % open PL (7)
@
>>0,(7) T:0.00@
<<PL_Put (7) a,b,c,d,e;
@
>>0, T:0.00@
<<RST_SI (3) (7) (6) % Simultaneous inequalities
@
>>0, T:82.36@
<<SC_Get (6)
@
>>0,{ { {-,-,+,+,+} , 2 }, { {+,-,-,+,+} , 2 }, { {+,+,-,-,+} , 2 }, { {-,+,+,+,-} , 2 },
{ {+,+,+,-,-} , 2 }} T:0.00@
<<Clear
@
>>0, T:0.00@
<<
Nop
End of RScyclic6.xcl
@
>>0, T:0.00@
<<Nop % (found EOF)@
>>0, T:0.00@
Quit@
>>0, T:0.00@
This output provides the following information:
frisco% PoSSoServer -p 5001
................................................................................
................................................................................
Server 5 connected to brutus.matesco.unican.es 8320
PoSSo Groebner server
Entering main loop
>> Nop
% PoSSo Server Test
% CountRoots for cyclic5
@
<< 0,@
................................................................................
................................................................................
Dimension of the associated Field : 70
Initialize the table xj*wi
Computation of the table xj*wi
Number of reductions to compute : 157
................................................................................
................................................................................
Modular search for separating element
-------------------------------------
Degree of the squarefree part : 15
variable 1 is not separating ... try with another one
Degree of the squarefree part : 15
variable 2 is not separating ... try with another one
Degree of the squarefree part : 15
variable 3 is not separating ... try with another one
Degree of the squarefree part : 15
variable 4 is not separating ... try with another one
Degree of the squarefree part : 15
variable 5 is not separating ... try with another one
No variable is separating ... Try non trivial vectors
Degree of the squarefree part : 1
not separating ... try with another one
Degree of the squarefree part : 70
I Have found a potential separating element
................................................................................
................................................................................
For example, apart from the dimension of the quotient ring, it is
shown that any of the variables is a separating element
for the considered polynomial system.
The different functionalities of RealSolving are described into the file main.dvi at the doc/RS directory. This document also describes how to use RealSolving separately from the PoSSoServer or the MuPAD interface (see Section 7.3), as a stand-alone application (together with Gb).
Information about the MPSolve package can be obtained from the web page of one of the authors, Dario Bini.
In the linux (and solaris) case, after using the gunzip and tar unix commands, the directory MPSolve2.0 is obtained with the following contents
gvega@brutus:/home/gvega/MPSolve2.0 > ls
DATA mpc.c mps_impr.c mps_sort.o mptemp.o test.pol
Makefile mpc.h mps_impr.o mps_star.c mt.c test.rur
README.TXT mpc.o mps_main.c mps_star.o mt.h testold.c
RESULTS mps.h mps_main.o mps_stio.c mt.o tools.c
gmptools.c mps_aber.c mps_newt.c mps_stio.o pl_out tools.h
gmptools.h mps_aber.o mps_newt.o mps_touc.c pl_solv.cpp tools.o
gmptools.o mps_clus.c mps_poly.c mps_touc.o pl_solv.h uni_solv.c
libmps.a mps_clus.o mps_poly.h mps_user.c rur_conv.c uni_solv.h
link.c mps_cnvx.c mps_poly.o mps_user.o rur_conv.h uni_solv.o
link.h mps_cnvx.o mps_solv.c mpsolve.tex rur_horn.c unisolve
link.o mps_glob.c mps_solv.o mptemp.c rur_solv.c
maketest mps_glob.o mps_sort.c mptemp.h rur_solv.h
In order to get the exec file need to run MPSolve, it is only required to do a ``make'' at the MPSolve2.0 directory. The only delicate point is the requirement that the GMP multiprecision package is correctly installed. This package can be obtained by anonymous ftp but its installation and configuration is out of the scope of these notes. The error message obtained if the gmp package is not installed is:
gvega@brutus:/home/gvega/MPSolve2.0 > make
gcc -I. -L. -O2 -c tools.c
gcc -I. -L. -O2 -c mt.c
gcc -I. -L. -O2 -c gmptools.c
In file included from gmptools.c:15:
gmptools.h:14: gmp.h: No such file or directory
In file included from mptemp.h:18,
from gmptools.c:16:
mpc.h:15: gmp.h: No such file or directory
make: *** [gmptools.o] Error 1
If the gmp package is installed properly then the unisolve exec file
is obtained after running the ``make'' command.
The syntax to use the unisolve exec file is as follows:
unisolve [options] < input_file
where the input file must have the following structure (extracted
from the README.TXT file in
the MPSolve2.0 directory):
! This is the Wilkinson polynomial of degree n ! defined by p(x)=(x-1)(x-2)...(x-n)
For example, the file mig2.pol in MPSolve2.0/Data contains one of the so-called Mignotte polynomials: a dense real polynomial with integer coefficients of degree 20
! mig2
! p(x)=x^17*(1+100 x)^3 + (100 x+1)^6
dri
0
20
1
600
150000
20000000
1500000000
60000000000
1000000000000
0
0
0
0
0
0
0
0
0
0
1
300
The directory MPSolve2.0/DATA contains a very useful set of examples
showing how to generate input files
for use by the unisolve exec.
The different options that can be given to the unisolve exec are described into the following list that has been also extracted from the README.TXT file in the MPSolve2.0 directory (``*'' denotes the default value):
Next we show how unisolve determines at least 100 digits of the complex roots (presented by their complex and real parts) of the polynomial
gvega@brutus: unisolve -o100 -Gi -Sa <DATA/mig2.pol
(-0.261328740991e1, 0.59695706056e0)
(-0.261328740991e1, -0.59695706056e0)
(-0.209526937806e1, 0.167263651042e1)
(-0.209526937806e1, -0.167263651042e1)
(-0.1161833132e1, 0.241702977645e1)
(-0.1161833132e1, -0.241702977645e1)
(-0.100000000000232079441674534712998293480334311182e-1,
0.401973384393657684282266347795725333e-13)
(-0.100000000000232079441674534712998293480334311182387522636e-1,
-0.40197338439365768428226634779572533253172696213982e-13)
(-0.1e-1, 0.e-74)
(-0.1e-1, 0.e-74)
(-0.1e-1, 0.e-74)
(-0.999999999995358411166509305740020530393e-2, 0.e-92)
(0.214283993e-2, -0.268270064488e1)
(0.214283993e-2, 0.268270064488e1)
(0.11661188249e1, 0.241702974953e1)
(0.11661188249e1, -0.241702974953e1)
(0.209955510001e1, 0.167263647685e1)
(0.209955510001e1, -0.167263647685e1)
(0.261757315522e1, -0.59695704562e0)
(0.261757315522e1, 0.59695704562e0)
The file README.TXT contains all the information required to start using the MPSolve package. More detailed information about the implementation and use of MPSolve can be obtained here or by running the ``make doc'' command in the MPSolve2.0 directory which generates the dvi file mpsolve.dvi.