[PPL-announce] Parma Polyhedra Library 0.7

[Roberto Bagnara]

We are very happy to announce the availability of PPL 0.7, the latest
release of the Parma Polyhedra Library.

The main focus of this release is a new configuration option that
enables the choice of different kinds of coefficients.  As an
alternative to the unbounded integer coefficients provided by the GMP
library, the user can now configure the PPL to use checked native
integers (8, 16, 32 or 64 bits wide).  The checked integer
coefficients apply systematic and efficient overflow detection,
raising an exception if the computed value cannot be represented by
the underlying type.  When the numerical coefficients involved are
likely to be small, the user can obtain significant efficiency
improvements while being sure that, if no exception is thrown, the
results are reliable.

This release also includes other important improvements ranging from
major efficiency gains (for all configurations) to usability and
portability.  Several bugs have been fixed and a more consistent
naming scheme for the library types has been adopted: as a result
users willing to upgrade will have to do a little renaming work on
their applications.  But it is worth the effort.

For more information, see below the list of main additions and changes
and visit the PPL web site at

        http://www.cs.unipr.it/ppl/

The core PPL development team:

       Roberto Bagnara  <bagnara at cs.unipr.it>
       Patricia M. Hill <hill at comp.leeds.ac.uk>
       Enea Zaffanella  <zaffanella at cs.unipr.it>


New and Changed Features
========================

o  The new configuration option `--enable-coefficients' allows for the
    use of alternative (integral) coefficient types.  Besides GMP
    integers, the user can now use checked native integers (8, 16, 32
    or 64 bits wide).  The use of such native coefficients is
    completely safe, since systematic (yet efficient) overflow
    detection is performed and, in case of overflow, an exception is
    raised.  GMP coefficients are used by default.

o  Significant efficiency improvements have been achieved everywhere.

o  We now require GMP 4.1.3 or higher.

o  The following classes have been renamed as indicated:

      AskTell            -> Ask_Tell
      BoundingBox        -> Bounding_Box
      ConSys             -> Constraint_System
      GenSys             -> Generator_System
      Integer            -> Coefficient
      LinExpression      -> Linear_Expression
      Polyhedra_PowerSet -> Polyhedra_Powerset
      PowerSet           -> Powerset
      SatMatrix          -> Saturation_Matrix
      SatRow             -> Saturation_Row

o  The helper function `widen_fun' has been renamed `widen_fun_ref'.

o  New assignment operators allowing to obtain an NNC_Polyhedron from a
    C_Polyhedron and the other way around.  In the latter case, the
    topological closure of the argument polyhedron is computed.

o  New explicit constructors and assignment operators allowing to obtain a
    Polyhedra_Powerset<NNC_Polyhedron> from a Polyhedra_Powerset<C_Polyhedron>
    and the other way around.  In the latter case, the topological closure
    of the element polyhedra is computed.

o  New explicit constructor Powerset<CS>::Powerset(const CS& d):  if `d'
    is not bottom, builds a powerset containing only `d';  builds the empty
    powerset otherwise.

o  New explicit constructor
    Polyhedra_Powerset<CS>::Polyhedra_Powerset(const PH& ph):  if `ph' is
    not empty, builds a powerset containing only `ph';  builds the empty
    powerset otherwise.

o  New method

      Polyhedra_Powerset::poly_difference_assign(const Polyhedra_Powerset& y)

    assigns to `*this' the poly-difference of `*this' and `y'.

o  All the public classes of the library have been endowed with methods

      memory_size_type total_memory_in_bytes() const

    and

      memory_size_type external_memory_in_bytes() const

    returning (lower bounds for) the total size in bytes of the memory
    occupied by *this and of the memory managed by *this, respectively.
    The type `memory_size_type' is a newly added unsigned integral type
    suitable to the representation of such information.

o  New method dimension_type Polyhedron::affine_dimension() returns
    the affine dimension of *this (not to be confused with the dimension
    of its enclosing vector space) or 0, if *this is empty.

o  All the methods changing (i.e., adding, removing, mapping, etc.)
    the dimensions of the vector space have been renamed so as to avoid
    any possible ambiguity with the affine dimension of the modified object.
    For instance,

      Polyhedron::add_dimensions_and_embed(dimension_type m);

    has been renamed as

      Polyhedron::add_space_dimensions_and_embed(dimension_type m);

o  The constructor C_Polyhedron(const NNC_Polyhedron& y) no longer
    throws an exception if `y' is not topologically closed.  Rather,
    it constructs a C_Polyhedron representing the topological closure
    of `y'.

o  The following constructors have been made explicit:

      Constraint_System::Constraint_System(const Constraint& c),
      Generator_System::Generator_System(const Generator& g),
      C_Polyhedron::C_Polyhedron(const Constraint_System& cs),
      C_Polyhedron::C_Polyhedron(const Generator_System& cs),
      C_Polyhedron::C_Polyhedron(Constraint_System& cs),
      C_Polyhedron::C_Polyhedron(Generator_System& cs),
      NNC_Polyhedron::NNC_Polyhedron(const Constraint_System& cs),
      NNC_Polyhedron::NNC_Polyhedron(const Generator_System& cs),
      NNC_Polyhedron::NNC_Polyhedron(Constraint_System& cs),
      NNC_Polyhedron::NNC_Polyhedron(Generator_System& cs).
      Polyhedra_Powerset<PH>::Polyhedra_Powerset(const Constraint_System& cs).

o  Functions in the C interface that compute (space) dimensions
    no longer return their result.  The caller is now required to pass,
    as an extra argument, a pointer to a memory area where the result
    will be written.  All the C interface functions now use the return
    value to signal the success or failure of the requested operation.

o  Now `make check' runs a number of tests with `ppl_lcdd', comparing
    the results to expected ones.

o  The `ppl_lcdd' demo is now able to parse problems produced by lrs,
    i.e., where the number of rows of the matrix is omitted and replaced
    by "*****" (five asterisks).

o  The enumeration values of enum Complexity_Class have been renamed
    POLYNOMIAL_COMPLEXITY, SIMPLEX_COMPLEXITY and ANY_COMPLEXITY.

o  In the Prolog interface, the predicates
    ppl_new_polyhedron_from_dimension/3 and
    ppl_new_polyhedron_empty_from_dimension/3 have been replaced by a
    single predicate ppl_new_polyhedron_from_space_dimension/4 where
    the (extra) third argument indicates whether the polyhedron to be
    created should be the universe or the empty polyhedron.

o  As the unary plus operator is not in standard Prolog, '+'/1 in linear
    expressions is no longer supported by the Prolog interface.


Bugfixes
========

o  Fixed a bug that was causing an unwanted exception to be thrown
    when adding to a C_Polyhedron some generators obtained from an
    NNC_Polyhedron (even though no closure point was being added).

o  Fixed a bug in the handling of empty generator systems having
    a strictly positive space dimension.

o  Fixed a bug that was affecting Polyhedra_PowerSet::geometrically_covers()
    and Polyhedra_PowerSet::geometrically_equals().

o  Method C_Polyhedron::H79_widening_assign() now widens the polyhedron
    itself instead of the homogenized polyhedral cone representing it.

o  Fixed a bug that was affecting Polyhedron::H79_widening_assign()
    as well as all the limited and bounded extrapolation operators.

o  Fixed a bug in Polyhedron::map_space_dimensions() that could manifest
    itself when used with a partial function encoding permutation.

o  Fixed a bug in the C interface function
    ppl_new_Linear_Expression_with_dimension().

o  Fixed a bug in the `ppl_lpsol' demo.

o  Fixed a bug in Polyhedron::is_universe() that could manifest itself
    when the polyhedron is described by a generator system that is
    not in minimal form.


-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it