[PPL-devel] PROBLEM with installation

[Roberto Bagnara]

Joycee Mekie wrote:
>     I could finally install PPL and use it also. There are a few
> queries that I have regarding the various algorithms in PPL. Could
> you kindly clarify my doubts or forward it to the person who
> is aware of the same.
> 
> I am using the
> 
> ppl_Polyhedron_map_dimensions(ppl_Polyhedron_t ph, ppl_dimension_type 
> maps[], size_t n)
> 
> function of PPL and would like to know the complexity (time and memore)
> of the same.

Dear Joycee,

the answer depends on how you measure the complexity and on which version
of the PPL you are using.

In general, mapping the dimensions requires a system of generators for
the polyhedron.  There are thus two cases.

If the polyhedron at hand comes with an up-to-date system of generators,
mapping dimensions has a complexity that is linear in the number of
generators.

If that is not the case (i.e., if the polyhedron only has an up-to-date
system of constraints) then the generators must be computed first and
this operation has, in the worst case, exponential complexity in the
number of constraints.  So this will dominate, in the worst case,
the cost of mapping dimensions.

The explanation above applies to PPL versions before 0.6 (I specify
this because you quoted a message dealing with the configuration
of PPL 0.5).  Starting with PPL 0.6, the case where the mapping
function is a permutation is handled specially, and never requires
the computation of a constraint or of a generator system.
More specifically, if the mapping function is a permutation:

1) if the constraint system is up to date, the polyhedron is mapped
    in linear time in the number of constraints;
2) if the generator system is up to date, the polyhedron is mapped
    in linear time in the number of generators;
3) if both are up to date, both are remapped as above.

The case where the mapping function is not a permutation is handled
the same way as before.

Please let me know if I answered your question or if, to the
contrary, I have been unclear.
All the best,

     Roberto

-- 
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