[PPL-devel] Exponential behavior in ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron

[Roberto Bagnara]

Hi Sebastian!

On 03/09/2010 05:06 AM, Sebastian Pop wrote:
> there seems to be an exponential behavior when calling
>
>    ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
>      (&ps, context);

This has indeed worst-case exponential complexity.  A powerset,
do to its nonredundancy property, should not contain empty elements.
So the implementation (lazily) performs an emptiness check,
whose complexity is exponential in the worst case.

> For now, I am thinking to limit the scops that we are handling based
> on the number of parameters that we have to handle to avoid for now
> this kind of problems.

This is one way to go.  Another way is to use the constructors with
limited complexity:

int
ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron_with_complexity
(ppl_Pointset_Powerset_C_Polyhedron_t* pph, ppl_const_Pointset_Powerset_C_Polyhedron_t ph, int complexity);

While the interfaces for these methods are all there, the implementation
is still incomplete: there are many places where we could honor the
PPL_COMPLEXITY_CLASS_SIMPLEX, expecially now that our implementation
of the simplex is being improved with sparse matrices.

Another possibility (which is actually the best one) would be for you to
begin using the deterministic timeout facilities we have added to the PPL
following the Graphite Workshop in Austin.  This would give you a general
solution for all your scalability problems.

> Roberto, is there some other output more interesting for the PPL folks
> and that I should report?

In this case it is not necessary, but in order for us to quickly
reproduce a problem, you could use the *ascii_dump() functions
to generate a text file that allow to reconstruct the PPL objects
you are observing.
Cheers,

    Roberto

-- 
Prof. Roberto Bagnara
Applied Formal Methods Laboratory
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it