[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Comparison with Polylib library

Our objectives to develop our own version was at that time (1999) to use a Polylib-like 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:

  1. we don't consider unions of polyhedra;
  2. we can use either machine or multi-precision integers;
  3. strict inequalities are implemented;
  4. 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;
  5. 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.
  6. 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.
  7. 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.
  8. we implements widening operators, as defined in cousot78,polka:fmsd:97.

This document was generated on October, 27 2006 using texi2html