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:
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.
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.
|TOP of page|
You may find here the source files for
POLYLIB - polylib5.0.tgz (251 Ko).
This are the C sources for the latest version of the Polylib.
Unix, Linux, Windows (with cygwin).
gcc, GNU make, GNU configure (mandatory)
GMP(GNU MP) (Optional, abitrary precision)
User's manual in available for download in the following formats:
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.
|Return to TOP|
In the year 2001 the teams involved in the Polylib development agreed the solution of a merge version of Polylib. For a good control of the code alterations, the idea of CVS repositories was accepted ( CVS is a Concurrent Version System and with his usage you can record the history of your source files).
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.
There is a PolyLib mailing-list in Strasbourg. To join the list, send an email to email@example.com containing the following message: SUB PolyLib firstname lastname organization.
The central CVS repository can be view through the web at : http://www.irisa.fr/cgi-bin/cvsweb.cgi/.
|Return to TOP|
The last version of Polylib contains contributions from different universities and research centers. It is clear that a
complete list of persons will be difficult to make, but we are trying to build it.
Three important parts must be mentioned when building such a list:
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:
|Return to TOP|
SPPoC: Symbolic Parameterized Polyhedral Calculator which can be find here also.
A link for polytope and polyhedron algorithms.
PORTA - POlyhedron Representation Transformation Algorithm.
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,
|Return to TOP|