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.