"scheduling" problem

[josephineyu]

Hi!
I have a problem of having more knowledge about a polytope making computation much much slower.
Here is a simple example: Take a cyclic polytope:

VERTICES
1 0 0 0
1 1 1 1
1 2 4 8
1 3 9 27
1 4 16 64

Suppose we know an inequality description but don't know that they're facets (although in this case, they all happen to be facets):
INEQUALITIES
0 2 -3 1
0 6 -5 1
0 12 -7 1
24 -26 9 -1
8 -14 7 -1
0 -4 5 -1

If you try to compute the f-vector giving only VERTICES, it takes less than 1 second, but if you give both VERTICES and INEQUALITIES, it takes 5 minutes!!
This is worrysome to me. Any suggestions? Let me know if I can be of any help in figuring out the problem. Thanks!
Josephine

[paffenholz]

The problem is basically known. There are combinations of properties, together with a target property that should be computed, that allow too many combinations of rules of almost equal complexity (in the weak sense polymake knows about algorithmic complexity of its computations). In your case, the scheduler tries to decide whether it is better to compute facets and the incidence matrix from vertices, or first reduce the inequalities. Together with the many rules that do the reduction or convex hull computation, this allows too many ways to arrive at F_VECTOR.

We are working on this issue, some future version of polymake will have a new implementation of the scheduler that can handle this.

Your combination of properties that lead to such a long computation for the scheduler is new (at least to me). We have "fixed" other such combinations by adjusting weights or rule targets/source. I will check whether I can also do this for the combination of VERTICES/INEQUALITIES. The computation of the F_VECTOR is correct in both ways, though.

You can release the burden of the scheduler by first asking for FACETS, and then for F_VECTOR. Similar tricks help if you find other bad combinations: First ask for a property that certainly needs to be computed in order to compute your target property.

[josephineyu]

That makes sense. I've never thought about complexity of scheduling. It's an interesting problem. Thanks for the reply!