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

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.

 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.

• I think the software Normaliz home.uni-osnabrueck.de/wbruns/normaliz might have an implementation of Hemmecke's algorithm. – Tony Huynh Mar 17 '15 at 16:30
• There is a similar algorithm implemented in Normaliz. As far as I know, the only implementation of my algorithm is by Matthias Walter in 4ti2 (www.4ti2.de), which still gives the state-of-the-art for the computation of Graver bases. When it comes to Hilbert bases, you should probably first try Normaliz. For extreme ray computations you may wish to try 4ti2's function 'rays', a very efficient implementation (by Peter Malkin) of my algorithm (which is in fact equivalent to the double description method). – Raymond Hemmecke Mar 26 '15 at 21:52

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.

• Many thanks for the reply, we want to use your algorithm to see if there is any way to program it in parallel (split the cones symmetrically and compute the intersection) or run it on a GPU. I have updated the question to make it clearer what I am stuck with – swistak Apr 15 '15 at 14:44
• @TomaszNguyen, let me briefly restate your problem: Given: rays generating a cone Find: Hilbertbasis of cone Solution: Use normaliz. It does exactly what you want: It runs in parallel. (It does not use my algorithmic approach, as this is a different problem.) My project-and-lift algorithm solves the following problem: Given: matrix A Find: Hilbertbasis of cone ker(A)\cap\Z^n_+ Solution: use normaliz or 4ti2 – Raymond Hemmecke Apr 22 '15 at 15:14
• So in the section 5.5 when you say I can compute the Hilbert basis of a cone (now I know it is Ax = 0) what do you mean by generators? Are these rays? (that's what I initially thought) or halfspace normals (would seem to make more sense, but still gives me an inequality) I might sound really stubborn, but my project brief was to use your algorithm to produce HB of any cone and after getting stuck trying to produce a sensible A out of a (not necessarily minimal) generating set, I would like to have absolute clarity about what you mean there. Many thanks – swistak Apr 25 '15 at 11:15