Joycee Mekie wrote:
I could finally install PPL and use it also. There are a fewqueries 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