[PPL-devel] PPL timings depend on sort (ordering) of input?

[Nestor Aguilera]

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

Thank you very much for your answers.

All the best,

                                               Néstor Aguilera