ResPol is a software to compute projections of the Newton polytopes of the
resultant of a given polynomial system, the dicriminant of a multivariate polynomial
or the principal A-determinant a.k.a. the secondary polytope.
This archive contains patches to sources of the CGAL library, the old experimental
CGAL packages Triangulation and Extreme points (not the one that are part
of the CGAL library, both were included here thanks to the kind permission of
its authors) and the respol sources. Both CGAL 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
version 4.14 available from https://github.com/CGAL/cgal/tree/v4.14).
You can follow these steps:
Follow the CGAL installation manual. It states that CGAL requires the
Boost libraries. In particular the header files and the threading library
binaries. 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
Download the LEDA library from https://www.algorithmic-solutions.com/index.php/products/leda-free-edition
Then copy the downloaded folder into external directory and rename it to leda.
In folder respol execute:
$ cmake -DCGAL_DIR=_YOUR_CGAL_PATH_ -Wno-dev -DCMAKE_BUILD_TYPE=Release .
$ make
where _YOUR_CGAL_PATH_ is the path where CGAL library was compiled.
For additional options, set by CMake flags, see README.FLAGS
(it is normally not needed to change default compilation options).
The following command will execute the test-suite
$ ctest
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
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 |), in this case, the non specialized coord's are the first from each support
(b) by defining an arbitrary projection, by giving the indices (starting at 0) of free parameters: those not included here are specialized,
(c) by providing only the symbol |.
Input example (file: inputs/cayley4_small.tmp)
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 -v 2 < resultant_examples/cayley4_small.tmp
The -v 2 verbose option will return information about the algorithm execution
and at the end the vertices of the computed polytope as well as the volume.
E.g. for the above command:
volume: 4575/1
The vertices of the resultant polytope:
[6,4,11,12],[0,0,0,30],[12,8,16,16],[12,8,8,16],[12,0,4,0],[6,0,4,0],[6,0,0,4],[0,0,3,12],[12,4,4,0],[12,8,0,24],[12,0,0,4],[12,0,8,0],[12,4,12,0],[6,0,7,0],[6,4,3,12],[0,0,0,15],[12,4,0,4],[0,0,6,12],[6,4,0,15],[6,4,11,12]
Using option -v with argument 1 we can have a compressed version of output
while with -v 0 we get only the number of output vertices (used by the test-suite).
respol can be used to compute discriminant and secondary polytopes. Example files are
in discriminant_examples and secondary_examples directories respectively.
Copyright (c) 2012-2019 Vissarion Fisikopoulos
Copyright (c) 2012-2019 Luis Penaranda
Maintainer: Vissarion Fisikopoulos
You may redistribute or modify the software under the GNU Lesser General Public License as published by Free Software Foundation, either version 3 of the License, or (at your option) any later version. It is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY.
The development started by Vissarion Fisikopoulos and Luis Penaranda while they were affiliated with University of Athens (UoA, Greece).
-
An oracle-based, output sensitive algorithm for projections of resultant polytopes.
I.Z.Emiris, V.Fisikopoulos, C.Konaxis, L.Peñaranda.
International Journal of Computational Geometry and Applications, vol. 23, pp. 397-423, World Scientific, 2013.
https://vissarion.github.io/publications/EFKP_IJCGA_13.pdf -
An output-sensitive algorithm for computing projections of resultant polytopes.
I.Z.Emiris, V.Fisikopoulos, C.Konaxis, L.Peñaranda.
Proceedings of 28th ACM Annual Symposium on Computational Geometry, 2012, Chapel Hill, NC, USA.
https://vissarion.github.io/publications/EFKP_SOCG_12.pdf