The core development team is very pleased to announce the availability
of PPL 1.0, a new release of the Parma Polyhedra Library.
This release includes support for the optimized representation of
sparse vectors of coefficients, achieving significant performance
improvements, e.g., when dealing with constraint systems describing
weakly relational abstractions such as boxes and octagonal shapes.
The precise list of user-visible changes is below.
For more information, please come and visit the new PPL web site at
http://bugseng.com/products/ppl
On behalf of all the past and present developers listed at
http://bugseng.com/products/ppl/credits and in the file CREDITS,
Roberto Bagnara Patricia M. Hill Enea Zaffanella Abramo Bagnara
BUGSENG srl
(http://bugseng.com)
--------------------------------------------------------------------------
NEWS for version 1.0 (released on June 28, 2012)
--------------------------------------------------------------------------
New and Changed Features
========================
o Significant improvements have been obtained in both time and space
resource usage by the definition of data structures and algorithms
for the case of "sparse rows", i.e., sequences of coefficients
where most of the values are zero.
o The library fully supports two different representations for rows:
the "dense" representation is an array-like representation tailored
to sequences having most of their coefficients different from zero;
the "sparse" representation saves memory space (as well as CPU
cycles) when most of the coefficients in the sequence are zero.
o A generic interface allows for a seamless interaction between the
dense and the sparse row representation. Most library entities
(linear expressions, constraints, generators, congruences, and
their systems) can be built using either representation, specified
as a constructor's argument.
o As a by-product of this sparse/dense refactoring work, efficiency
improvements have been obtained even for those computations that
are still based on the dense row representation.
o Reasonable default values for the row representation are provided
for each library entity, automatically leading to significant
memory space savings even in old client/library code, e.g., when
dealing with constraint systems describing weakly relational
abstractions such as boxes and octagonal shapes.
o If desired, these default values can be customized to user's needs
by changing just a few lines of library code. For instance, the
constraint systems stored inside C_Polyhedron and NNC_Polyhedron
objects can be made to use the sparse representation by just
changing the following line in Polyhedron.defs.hh:
static const Representation default_con_sys_repr = DENSE;
to become
static const Representation default_con_sys_repr = SPARSE;
Bugfixes
========
o Fixed a bug affecting methods
bool BD_Shape<T>::contains(const BD_Shape& y) const;
bool Octagonal_Shape<T>::contains(const Octagonal_Shape& y) const;
whereby the wrong result was obtained when *this is an empty
weakly-relational shape and y is not empty.
o Fixed a bug affecting the PIP solver whereby a wrong result could have
been obtained if the input constraint system contained multiple linear
equality constraints.
--
Prof. Roberto Bagnara
Applied Formal Methods Laboratory - University of Parma, Italy
mailto:bagnara@cs.unipr.it
BUGSENG srl - http://bugseng.com
mailto:roberto.bagnara@bugseng.com
