PPL-announce

Download

ppl-announce@bugseng.com

December 2004

1 participants
1 discussions

Parma Polyhedra Library 0.7
by Roberto Bagnara 24 Dec '04

24 Dec '04

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(a)cs.unipr.it> Patricia M. Hill <hill(a)comp.leeds.ac.uk> Enea Zaffanella <zaffanella(a)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@cs.unipr.it

1 0