Description
Polylib is a free library written in C for the manipulation of polyhedra. The library is operating on objects like vectors, matrices, lattices, polyhedra, Z-polyhedra, unions of polyhedra and a lot of other intermediary structures. It provides functions for all the important operations on these structures.
The current version of Polylib is : polylib5.0.tgz (251 Ko)
The library was first developed by Hervé Leverge and Doran Wilde at IRISA-INRIA, in Rennes, France, based on the Chernikova algorithm. N. V. Chernikova rediscovered in fact the double description representation introduced by Motzkin which shows the duality between the geometric representation of a list of constraints provided as linear systems of equations and inequalities on one hand and the representation by a finite set of vertices, rays and lines on the other hand. A powerful library has to handle both representations in order to allow easy polyhedra manipulation. Important improvements were made in the conversion process between these representations by H. Le Verge and D. K. Wilde then Polylib was extended to handle parameterized polyhedron, Ehrhart polynomials (Vincent Loechner) and Z-polyhedra (Tanguy Risset). Philippe Clauss is the one who first signaled the possibility of counting the number of integer points in a union of rational convex polytopes by a special kind of polynomial called Ehrhart polynomial.
Polylib is using a double description form for a polyhedron in which the constraints and the generators are present. All polyhedral operations are done with the optimal schemes and after the number of conversions is minimized.
The most common structures the ``Polyhedral Library'' is operating with are called domains, and consists of unions of polyhedra. Examples of domain operations which can be performed by the library are:
- Image;
- Preimage;
- Intersection;
- Difference;
- Union;
- ConvexHull;
- Simplify.
Applications
Much work has been done in the development of methods to do synthesis, analysis and verification of systems of recurrence equations in order to find equivalent parallel forms of these algorithms suitable for implementation. The ultimate goal is to transform an algorithm from a mathematical type of description into an equivalent form that can be implemented either with special purpose hardware (with systolic arrays for instance), or as a program that is able to run on a multiprocessor system.
Since polyhedra are used to represent the iteration domains of nested loop programs, procedures for operating on polyhedra are useful for doing loop transformations and other program restructuring transformations which are needed in parallelizing compilers. Thus a need for a library of polyhedral operations has been recognized in the parallelizing compiler community.
The Alpha language was invented to be able to do this very kind of program transformation. The work presented here was initiated in connection with the implementation of an Alpha environment.
VisuDomain is an extension to the PolyLib that permits to visualize union of parameterized domains (you can use it to visualize single non-parameterized polyhedra too of course).
Polyhedra have been studied also in other several fields. Many applications found in polyhedra a way to solve different problems and Polylib can be a good tool on this purpose.
- From the geometric point of view by computational geometrists. The main areas to be covered are the convex hull computation of a finite point set, the vertex enumeration for a convex polytope, the computation of Voronoi diagram and Delaunay triangulation.
- A very important area of applications is the one of program optimization. For nested loop programs, the iteration spaces can be modeled by polyhedra and systems of rational linear constraints. A new trend is the compilation and optimization for software controlled memory systems.
- From the algebric point of view it is one of the most promising approaches to attack combinatorial optimization problems.Polyhedral investigations are the theoretical basis of the so-called cutting plane algorithms and separation problems.
- From the structural/lattice point of view by the combinatorics community with applications in discrete dynamical systems.
History
Polylib was first developed IRISA, in Rennes, in connection with the ALPHA project.
This first version (1.1) manipulates non-parameterized unions of polyhedra through the following operations: intersection, difference, union, convex hull, simplify, image and preimage, plus some input and output functions. The polyhedra are computed in their dual implicit and Minkowski representations, in homogeneous spaces.
Version 2 of the PolyLib included parameterized vertices computation.
PolyLib 3.14 includes Ehrhart polynomials computation, which allows counting the number of integer points contained by a parameterized polyhedron. This part is a Strasbourg team contribution together with VisuDomain extension.
PolyLib 4 included the GNU MP library (as a compilation option), and 64 bits computations, in order to avoid integer overflows.
Polylib 5 is a merger of Strasbourg, Rennes and BYU Polylib. There is now a central CVS repository in Rennes, IRISA
Both Strasbourg and Rennes teams have plans for future development of the library. The points that will be the subject of research are Ehrhart polynomials, Z-polyhedra but also the interface.
POLYLIB - polylib5.0.tgz (251 Ko).
This are the C sources for the latest version of the Polylib.
Targeted Platforms
Unix, Linux, Windows (with cygwin).
Software/Hardware Requirements
gcc, GNU make, GNU configure (mandatory)
GMP(GNU MP) (Optional, abitrary precision)
Documentation
User's manual in available for download in the following formats:
| DVI | PostScript |
You can download the user's manual in HTML format: DOC.tar.gz or you can browse it on-line.
License
Permission is granted to copy, use, and distribute for any commercial or noncommercial purpose under the terms of the GNU General Public license, version 2, June 1991.
In these conditions the development of the software is made in a safer way. The access on the CVS repositories for updating or comparing different versions is made with a login and a password. For this purpose you must contact IRISA representatives, as the permission is restricted to developers. One possible way is by contacting the Polylib administrator.
You may also contact Vincent Loechner or Tanguy Risset for any information, bug report, compilation problems, ...
There is a PolyLib mailing-list in Strasbourg. To join the list, send an email to sympa@u-strasbg.fr containing the following message: SUB PolyLib firstname lastname organization.
In January 2001 a forum group of the Polylib community was set up. You may subscribe to the group in order to be able to have full contact with the Polylib world.
The central CVS repository can be view through the web at : http://www.irisa.fr/cgi-bin/cvsweb.cgi/.
- Tanguy Risset, Patrice Quinton - Project COSI(former API) - IRISA (Universite de Rennes I, France)
- Doran Wilde - BYU - USA
- Vincent Loechner - LSIIT/ICPS - ULP (Strasbourg, France)
The principles and the mathematical theory which form the Polylib background are very well presented in the following articles, each one representing a trend in Polylib development:
| File | Name | Authors |
|---|---|---|
| Polylib.ps | "A Library For Doing Polyhedral Operations" | Doran K. Wilde |
| Z-polylib.ps | "A library for Z-Polyhedral operations" | Sundi Phani Kumar Nookala and Tanguy Risset |
| ZPol1.ps | "On manipulating Z-Polyhedra" | Patrice Quinton, Sanjay Rajopadhye and Tanguy Risset |
| ehrhart.ps | "Polylib:A library for Manipulating Parametrized Polyhedra" | Vincent Loechner |
| Cher.ps | "A note on Chernikova's alghorithm" | H. Le Verge |
Ehrhart Polynomials Page, by Philippe Clauss, and related publications.
ULP-Strasbourg Polylib Page, Vincent Loechner
SPPoC: Symbolic Parameterized Polyhedral Calculator which can be find here also.
A link for polytope and polyhedron algorithms.
PORTA - POlyhedron Representation Transformation Algorithm.
Program compilation and optimization
The Omega project
The CDD software based om Double Description method of Motzkin.
Another polyhedra library developed under C++.
K. Fukuda. Polyhedral computation FAQ. Swiss Federal Institute of Technology, Lausanne and Zurich, Switzerland,