ResPol is a software to compute a projection of the Newton polytope of the
resultant of a given polynomial system.
This archive contains patches to the sources of the CGAL library, the
experimental CGAL packages "Triangulation" and "Extreme points" (not yet
part of the CGAL library, both were included here thanks to the kind
permission of its authors) and the ResPol sources. Both CGAL library and
ResPol are written in C++.
To compile and use ResPol, you need first to compile the CGAL library, or
download the precompiled library (this software has been tested with CGAL
3.6 and newer versions). You can follow these steps:
------------------------
1. Compile CGAL sources
------------------------
Follow the CGAL installation manual. It states that CGAL requires the Boost
libraries. In particular the header files and the threading library
binaries. Version 1.39 (or higher) are needed. Having GMP version 4.2 or
higher and MPFR version 2.2.1 or higher installed is recommended by CGAL
but needed by ResPol. Once you have installed these libraries, execute:
$ cmake .
$ make
--------------------------
2. Compile ResPol sources
--------------------------
In folder respol/examples execute:
$ cmake -DCGAL_DIR=_YOUR_CGAL_PATH_ .
$ make
where _YOUR_CGAL_PATH_ is the path where CGAL library was compiled. For
additional options, set by CMake flags, see the file README.FLAGS (it is
normally not needed to change default compilation options).
--------------
3. Use ResPol
--------------
Then, you can test the code with some inputs from the examples/input
directory. The format of the input files is:
1st line: dimension (i.e. the number of the system variables)
2nd line: the cardinalities of the supports '|' the projection
3rd line: the support points
ResPol supports:
(a) computations of projections defined by implicitization problems
(b) computations of arbitrary projections
(c) generic resultant polytope computations
(d) computation of (projections of) discriminant polytopes (currently supported only using "tropli_disc" software; see below for more details)
The second line of the input file defines the projection and actually
selects one of the above options. (a) is supported by not defining any
projection (omitting '|'), (b) by defining an arbitrary projection and (c)
by providing only the symbol '|'.
-----------------------------
3.1. Implicitization example:
-----------------------------
## file: inputs/cayley4_small_implic.txt ##
3
3 3 3 3
[[0, 0, 0],[1, 2, 1],[0, 2, 4], [0, 0, 0],[0, 1, 3],[2, 4, 0], [0, 0, 0],[0, 0,
1], [2, 0, 0], [0, 0, 0], [0, 1, 4],[0, 1, 5]]
##############
This input belongs to the case (a) i.e implicitization. By adding "| 0 2 5
6 7 8 9" in the second line, we are in the case (b) i.e. arbitrary
projection. On the other hand, by adding only "|" we are in the case (c)
i.e. generic resultant polytope.
To run ResPol with this input execute:
$ ./res_enum_d < inputs/cayley4_small_implic.tmp
-----------------------------
3.1. Discriminant example:
-----------------------------
* IMPORTANT: To compute discriminant polytopes the software "tropli_disc" by Felipe Rincon
* is needed, which is available from
* http://homepages.warwick.ac.uk/staff/E.F.Rincon/tropli/
* Compile "tropli_disc" or download the binary file available from the webpage above
* and put the executable in the same folder as res_enum_d executable.
## file: inputs/example2mega.txt ##
1
5 0 |
[[0],[1],[2],[3],[4]]
##############
This input belongs to the case (d) i.e discriminant polytopes. By adding "| 0 2 5
6 7 8 9" in the second line, we are able to compute a projection of the discriminant
polytope on the specified coordinates.
To run ResPol with this input execute:
$ ./res_enum_d -d < inputs/example2mega.txt
----------------
4. ResPol output
----------------
ResPol by default outputs the vertices of the computed polytope.
Alternatively running the command:
./res_enum_d -v 1 < inputs/cayley4_small_implic.tmp
the output of the program has this form:
6 4 4 12 12 31 19 -1 0.74 0.05 0 -2 109800/1
The meaning of each value follows (the notation on the paper is used).
-column 1: Cayley dimension (d in the paper)
-column 2: ambient dimension of Q (m in the paper)
-column 3: dimension of Q
-column 4: cardinality of A
-column 5: cardinality of A after preprocessing
-column 6: number of computed triangulations
-column 7: number of vertices of Q
-column 8: number of extreme vertices of Q (or -1 if not computed)
-column 9: overall time
-column 10: time spent in the computation of convex hull of Q
-column 11: time spent in the offline computation of Q
-column 12: total time spent in determinant computations
-column 13: volume of Q (or -1 if not computed)
