Q:

Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm

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:

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}
$$
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.

A:

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.

