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

[Enea Zaffanella]

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.

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.

Cheers,
Enea.