Comparison with Polylib library
Our objectives to develop our own version was at that time (1999) to use
library with multi-precision integers, and secondary to implement some
parts differently. Our library is also more simpler because we don't
consider explicit unions of polyhedra as in IRISA's library.
The main differences are sketched below:
- we don't consider unions of polyhedra;
- we can use either machine or multi-precision integers;
- strict inequalities are implemented;
- conversion and minimization operations can be delayed; IRISA's
library always keep both representation, whereas we keep ordinary only
one and do a conversion only when it is mandatory, for example when we
wants to intersect polyhedra whose constraints are not available; when
both representations are available, they are necessarily minimal, butthat's not the case when only one is available;
- when both representations are available for a polyhedra, we keep
also the saturation matrix. This allows to perform intersection and
convex hull with another polyhedron in an quite incremental way, because
we don't compute it again.
- in some case of variable assignation or substitution on a
polyhedron, when the transformation is inversible, we operate on both
representation if they were already available; it is the case too for
the embeding or projection into a space with supplementary dimensions.
- when we do the conversion from constraints to generators, for
instance, we obtain a minimal set of the generators, but the set of
constraints is still not minimal. The algorithm which perform this
minimization seems to me cheaper that the one of IRISA; I must confess
however that I have not fully understood the IRISA's algorithm.
- we implements widening operators, as defined in
This document was generated
on October, 27 2006