[Math] Computation of extreme rays of rational polyhedral cones – Hemmecke’s project and lift algorithm

computer-algebraconvex-polytopeslinear algebralinear programmingmonoidal-categories

I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105

Unfortunately I am struggling to make the algorithm work on the simple examples. Consider a cone given by a bunch of vertices in $\mathbb{R}^2$:

$$
\begin{bmatrix}
4&2\\
2&1\\
2&2\\
0&1\\
\end{bmatrix}
$$

http://i.stack.imgur.com/zwNk4.png:

       


               
(Image added by J.O'Rourke.)

There are several things blocking me at the moment:

  1. In his paper Raymond Hemmecke assumes that any cone has generators given in Hermite Normal Form. Since HNF are a result of a unimodal transformation of a matrix, I should be able to transform any set of generators into HNF invertibly. But does that also hold for the minimal generating sets obtained from the HNF? I.e. if I use a HNF of a cone to obtain the minimal generating set, will I always be able to transform the result back to the minimal generating set of the original cone? Here's how the generators of cones and lattices are described by Hemmecke in $\mathbb{R}^n$:
    $$
    \begin{matrix}
    p_1 &= &(p_{1,1},&p_{1,2},&…,&…,&p_{1,r},&…s,&p_{1,n})\\
    p_2 &= &(0,&p_{2,2},&…,&…,&p_{2,r},&…,&p_{2,n}) \\
    p_3 &= &(0,&0,&p_{2,2},&…,&p_{2,r},&…,&p_{2,n})\\
    &\vdots&(\vdots,&\vdots,&…,&\ddots,&\vdots,&…,&\vdots)\\
    p_r &= &(0,&0,&…,&0, &p_{r,r}, &…, &p_{r,n})\\
    \end{matrix}
    $$

  2. For the computation of the extreme rays of a cone, I end up with misshapen cones/lattices
    Hemmecke defined a cone $\Gamma$ the following way

Let
$$
L = span(p_i),\quad p_i \in \mathbb{Z}^n.
$$
Then:
$$
\Gamma = L \cap \mathbb{R}^n_+
$$

But my cone above does not include all of the points in the positive orthant! So when I span a lattice with the generators $p_i$ and intersect it with the positive orthant, I still end up with lattice points that are not in my cone.

Does anyone have any experience with the ray algorithm? I have looked at the Macaulay implementation, but it uses Fourier-Moutzkin, I would like to use the method described by Hemmecke, but unfortunately I think I am missing something. I have tried running 4ti2 on these examples, but I get no results at all – the program returns an empty generating set.

[edit]
The goal is to use the algorithm to compute the Hilbert basis given the generators of a cone, like in section 5.5 of the paper. I.e. given the picture above, get me the Hilbert basis of the red area. With the homogeneity restriction I struggle to define my generating sets in a sensible way – I am given the vectors in the kernel, but I don't have the linear map $A$. If my input consists of 4 2-dimensional vectors like above, I can't possibly come up with a map from $RR^2$ to $RR^2$ that the red cone as its kernel. My supervisor said I am going to need to embed it in a higher dimensional space, but I don't really see how to do it sensibly.

One possible set of rays or $\mathbb{R}$-generators of the cone above is (reading as rows)
\begin{bmatrix}
2&1\\
0&1\\
\end{bmatrix}
This doesn't satisfy $Ax= 0\quad x \geq 0$. On another hand this cone is uniquely defined by the y axis and the ray bisecting the cone into two equal pieces (or a halfspace defined by the normal vector that bisects the cone), is that how I bring it to a homogenous system?

To put it more clearly, I want to compute the Hilbert basis of the red cone, but I do not know the linear transformation that has the red cone as its kernel. All I have is a (not necessarily minimal) generating set of points of the cone.

Best Answer

Tomasz, I think you are mixing something here. You wish to compute the extreme rays of a cone given by generators? (This would mean you wish to throw away redundant generators, right?)

However, the algorithm that you wish to implement does something completely different! It takes a system $Ax=0$, $x\ge0$ (defining a pointed rational cone) and computes the cone generators or the Hilbert basis, in case you are interested in the integer situation.

In the case of $Ax=0$, $x\ge0$, it takes generators of $Ax=0$ and brings those into HNF. Then all works out nicely.

Hope that helps.

Raymond

PS: If you wished to compute the Hilbert basis of a cone given by cone generators, I recommend using Normaliz.

Related Question