2
$\begingroup$

I tried to use qhalf, but found bug in its output for 8 dimensions. Parma polyhedra library seemed to be more credible, but it gives wrong results even in 6 dimensions. Input central hyperplanes for chamber:

[-1, 1, 1, 1, 1, -1], 
[-1, -1, 1, 1, 1, 1], 
[1, -1, -1, 1, 1, 1], 
[1, 1, -1, -1, 1, 1], 
[1, 1, 1, -1, -1, 1], 
[1, 1, 1, 1, -1, -1]

Facets are the same, and polyhedron.vrep() is equal to

[[ 0  1 -1  1 -1  1 -1]
 [ 1  0  0  0  0  0  0]
 [ 0  1  0  1  0  1 -1]
 [ 0  1  0  0  1  0  0]
 [ 0  1  0  1  0  0  0]
 [ 0  1  0  1 -1  1  0]
 [ 0  0  0  1  0  0  1]
 [ 0  0  0  1  0  1  0]
 [ 0  1  0  1 -1  2 -1]
 [ 0  0  0  0  1  0  1]
 [ 0  1  0  0  0  1  0]]

which is clearly wrong, because vertices should be symmetric relative to cyclic change of coordinate axes.
What library can you suggest which is more reliable?

$\endgroup$
  • $\begingroup$ you should provide input, and an explanation of what one should expect as output. $\endgroup$ – Dima Pasechnik Aug 26 '17 at 14:45
  • $\begingroup$ I'm not using PPL now and cannot do what you propose. $\endgroup$ – DSblizzard Aug 26 '17 at 14:52
  • $\begingroup$ it is not clear from your question what kind of polyhedron you are trying to build and what kind of input you are giving. You might use e.g. sagemath, which uses ppl as a default backend for polyhedral constructions. Give a mathematically meaningful description in any case, not just lament about bad software... $\endgroup$ – Dima Pasechnik Aug 26 '17 at 14:58
  • $\begingroup$ Given normal vectors define half-spaces, intersection of which gives polyhedron (H-representation). $\endgroup$ – DSblizzard Aug 26 '17 at 15:04
  • $\begingroup$ halfspaces through the origin? chances are you needed a column of 0s to indicate this. I will check once I get to a computer... $\endgroup$ – Dima Pasechnik Aug 26 '17 at 15:07
2
$\begingroup$

No, there is no bug in PPL (Parma Polyhedral Library) here. Here is why.

Let $A$ be the first of your matrices. Note that for $\ell=(1, -1, 1, -1, 1, -1)$ one has $A\ell=0$, and in fact $\ell$ spans the kernel of $A$. Thus your polyhedron is the Minkowski sum of the line spanned by $\ell$ and pointed cone $C$ given by the 12 inequalities, 6 of the form $\langle a_i,x\rangle\geq 0$ coming from the rows $a_i$ of $A$, and 6 of the form $x_j\geq 0$, for $1\leq j\leq 6$.

To enter your data in a typical polyhedral solver in "H-representation", you'd have to add the 1st column of 0s to $A$- as the rows are interpreted as inequalities, with the 1st entry of each row being the right hand side of the inequality. That is, as follows:

A=[[0, -1, 1, 1, 1, 1, -1],
   [0, -1, -1, 1, 1, 1, 1],
   [0, 1, -1, -1, 1, 1, 1],
   [0, 1, 1, -1, -1, 1, 1],
   [0, 1, 1, 1, -1, -1, 1],
   [0, 1, 1, 1, 1, -1, -1]]

Now, I'll give the input for Sagemath system, where you can in fact choose from a number of polyhedral backends (the default is PPL, one you accuse of being buggy.)

sage: p=Polyhedron(ieqs=A); p
A 6-dimensional polyhedron in QQ^6 defined as the convex hull of 1 vertex, 9 rays, 1 line
sage: p.lines()
(A line in the direction (1, -1, 1, -1, 1, -1),)
sage: p.vertices()
(A vertex at (0, 0, 0, 0, 0, 0),)
sage: p.rays()
(A ray in the direction (1, 0, 1, 0, 1, -1),
 A ray in the direction (1, 0, 0, 1, 0, 0),
 A ray in the direction (1, 0, 1, 0, 0, 0),
 A ray in the direction (1, 0, 1, -1, 1, 0),
 A ray in the direction (0, 0, 1, 0, 0, 1),
 A ray in the direction (0, 0, 1, 0, 1, 0),
 A ray in the direction (1, 0, 1, -1, 2, -1),
 A ray in the direction (0, 0, 0, 1, 0, 1),
 A ray in the direction (1, 0, 0, 0, 1, 0))

At this point one might say: "oh, the output is wrong, as the cyclic symmetry is lost!". But in fact it is OK, as each ray is only defined up to a linear combination with $\ell$; and indeed you can see that the 1st ray $(1, 0, 1, 0, 1, -1)$ becomes $(0,1,0,1,0,0)$ if one subtracts $\ell$, similarly the 4th becomes $(0,1,0,0,0,1)$ and the 7th becomes $(0,1,0,0,1,0)$. That is, one can represent all the 9 rays as 0-1 vectors with just two 1s, and the cyclic symmetry is still there; there is no bug here, it's just the way the output is encoded is a bit counter-intuitive. In fact, one can check that this is all correct, by adding the inequalities specifying nonnegativity of the variables to $A$, computing the corresponding pointed cone $C$, and the Minkowski sum of $C$ and $\ell$, as follows:

sage: B=matrix(A).stack(matrix.zero(1,6).stack(matrix.identity(6)).T)
sage: pp=Polyhedron(ieqs=B); pp; pp.rays()
A 6-dimensional polyhedron in QQ^6 defined as the convex hull of 1 vertex and 9 rays
(A ray in the direction (0, 0, 0, 1, 0, 1),
 A ray in the direction (0, 0, 1, 0, 1, 0),
 A ray in the direction (1, 0, 0, 0, 1, 0),
 A ray in the direction (0, 1, 0, 0, 1, 0),
 A ray in the direction (0, 0, 1, 0, 0, 1),
 A ray in the direction (0, 1, 0, 0, 0, 1),
 A ray in the direction (1, 0, 1, 0, 0, 0),
 A ray in the direction (0, 1, 0, 1, 0, 0),
 A ray in the direction (1, 0, 0, 1, 0, 0))
sage: pp.Minkowski_sum(Polyhedron(lines=p.lines())).inequalities()
(An inequality (-1, -1, 1, 1, 1, 1) x + 0 >= 0,
 An inequality (1, 1, -1, -1, 1, 1) x + 0 >= 0,
 An inequality (1, -1, -1, 1, 1, 1) x + 0 >= 0,
 An inequality (-1, 1, 1, 1, 1, -1) x + 0 >= 0,
 An inequality (1, 1, 1, 1, -1, -1) x + 0 >= 0,
 An inequality (1, 1, 1, -1, -1, 1) x + 0 >= 0)

And the latter is exactly the original 6 inequalities.

$\endgroup$
  • $\begingroup$ It's not a bug, but it's not OK either. I won't argue, it's just my humble opinion. $\endgroup$ – DSblizzard Aug 27 '17 at 7:33
  • 1
    $\begingroup$ What are you complaining about? Unless the software either recognises the underlying symmetry (a very hard problem) or takes the symmetry as extra input, there is no way you would see the symmetry in the output. So this is a different problem all together. But PPL solves the problem you pose to it just fine. $\endgroup$ – Dima Pasechnik Aug 27 '17 at 7:39
  • $\begingroup$ One thing that should be doable is Minkowski difference computation; Minkowski difference of the polyhedron and $\ell$ would produce cleaner output, but in Sagemath you can only subtract a compact polyhedron. Patches fixing this are welcome! $\endgroup$ – Dima Pasechnik Aug 27 '17 at 7:46
  • $\begingroup$ Input hyperplanes fully define polyhedron (and all its rays). In the output this unambiguity is lost and we have many possible polyhedrons. $\endgroup$ – DSblizzard Aug 27 '17 at 7:46
  • $\begingroup$ nothing is lost- the vertices and rays in the output are only defined up to a vector in the subspace summand. This is mathematically fully correct. $\endgroup$ – Dima Pasechnik Aug 27 '17 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.