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.

Normalizhome.uni-osnabrueck.de/wbruns/normaliz might have an implementation of Hemmecke's algorithm. $\endgroup$ – Tony Huynh Mar 17 '15 at 16:30