Il 01/10/2011 16:03, Nestor Aguilera ha scritto:

Hi Enea,

Thank you very much for your answers.

On 29 Sep 2011, at 16:23, Enea Zaffanella wrote:

...

Il 28/09/2011 22:56, Nestor Aguilera ha scritto:

...

Hi,

I am new to PPL, coming from CDD (and PORTA), and I am using "ppl_lcdd" (replacing "lcdd_gmp").

I found PPL quite fast on my problems as compared to CDD, so I am quite happy with it.

However, working with circulant matrices I found that the timings depend very much on how the problem is presented.

I am enclosing two files with the same vertices: those in the "ppl_7.ext" are those in "ppl_1.ext" rotated by 6 places, and the problem is to find the inequalities description of the convex hull.

In my machine, "ppl_lcdd" takes about 1.2s to solve "ppl_1" and about 18.3s to solve "ppl_7", although they are essentially the same problem.

Can anyone tell me why this is so?, does it depend on any special sorting in the input?

Thank you very much.

Néstor Aguilera

Hello Néstor.

I have not checked carefully your input files, but I guess that when you say "rotated by 6 places" you are meaning that the space dimensions in the input polyhedron (i.e., the columns of the matrices) have been subject to a permutation.

That is right, although I might add that the permutation is cyclic.

For example, in the .ext representation, the point

1 1 0 0 0 0 1 0 0 0 0 0

in one file goes to

1 1 0 0 0 0 0 1 0 0 0 0

in the other file.

...

If that is the case, then some difference in the time needed to perform a conversion is to be expected.

The PPL library (like other polyhedra libraries) speculatively sorts the input representation using (a variant of) a lexicographic ordering. This is a known heuristics that quite often is successful in reducing the size of intermediate conversion results (and hence, computation time). In unlucky cases, the heuristics may be less effective or even totally ineffective ... but usually it behaves as a significant improvement.

Thanks, I understand that.

However, I would have guessed that the sorting procedure on both inputs would take very little time (much less than a second for my inputs) and should take about the same timings once done. Recall that in my test files and my machine, PPL takes about 1.2 seconds for one file and 18.3 seconds for the other, more that 10 times the first one and way beyond what sorting would take.

Could you elaborate a little more on the sorting used (the variant of lexicografphic order)? E.g., does it include the support (for instance, (1,0,0) comes before (0,1,1) unlike the lexicographic order)?, is it dynamical or done only once at the beginning?, is there a way I could "preprocess" and test my files looking for a "good" sorting procedure (perhaps without PPL doing the sorting)?

The sorting procedure used by the PPL only sorts the *rows* of the matrix. Since you are permuting the columns, the sorting procedure will *not* yield the same result for the two inputs you are mentioning. In practice, this means that it is not the sorting being slow in your second example; rather, it is the incremental conversion procedure that happens to generate (much) bigger intermediate results.

Regarding the details of the row comparison function used in the PPL, see the documentation of

int compare (const Linear_Row &x, const Linear_Row &y)

http://bugseng.com/products/ppl/documentation//devref/ppl-devref-0.11.2-html...

Currently there is no support for dynamically changing this comparison function. We might want to consider such an addition, if someone provides us evidence of the effectiveness of the approach.

If you want to perform experiments with a different comparison function, you can simply replace the default one. Note however that there are places where we may have made assumption about sortedness: e.g., we may have assumed that in a sorted constraint system all equalities come before all inequalities.

If you want to perform experiments with a different ordering of space dimensions (i.e., columns), then you might be interested in the following method:

template<typename Partial_Function > void Polyhedron::map_space_dimensions (const Partial_Function &pfunc)

For its documentation (in particular, for the specification of the partial function that, in your case, should be a total function encoding a permutation), see the PPL manual.

Cheers, Enea.

Thank you very much for your answers.

All the best,

Néstor Aguilera