Hi Sebastian!
On 03/09/2010 05:06 AM, Sebastian Pop wrote:
there seems to be an exponential behavior when calling
ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&ps, context);
This has indeed worst-case exponential complexity. A powerset, do to its nonredundancy property, should not contain empty elements. So the implementation (lazily) performs an emptiness check, whose complexity is exponential in the worst case.
For now, I am thinking to limit the scops that we are handling based on the number of parameters that we have to handle to avoid for now this kind of problems.
This is one way to go. Another way is to use the constructors with limited complexity:
int ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron_with_complexity (ppl_Pointset_Powerset_C_Polyhedron_t* pph, ppl_const_Pointset_Powerset_C_Polyhedron_t ph, int complexity);
While the interfaces for these methods are all there, the implementation is still incomplete: there are many places where we could honor the PPL_COMPLEXITY_CLASS_SIMPLEX, expecially now that our implementation of the simplex is being improved with sparse matrices.
Another possibility (which is actually the best one) would be for you to begin using the deterministic timeout facilities we have added to the PPL following the Graphite Workshop in Austin. This would give you a general solution for all your scalability problems.
Roberto, is there some other output more interesting for the PPL folks and that I should report?
In this case it is not necessary, but in order for us to quickly reproduce a problem, you could use the *ascii_dump() functions to generate a text file that allow to reconstruct the PPL objects you are observing. Cheers,
Roberto