\NeedsTeXFormat{LaTeX2e}
\documentclass[twoside,12pt]{article}
\usepackage{amsmath,amssymb,amsthm,multicol}

\usepackage{mathptmx}
\let\boldsymbol=\pmb

% \pagestyle{headings}
%\usepackage{headings}
\usepackage{url}

% \hfuzz 1pt
% \overfullrule 3pt

\parindent 0em
\parskip 1ex plus.5ex minus.25ex
\hoffset -1in
\oddsidemargin 30mm
\evensidemargin 25mm
\textwidth 155mm
\voffset -1in
\topmargin 14mm
\headheight 4mm
\headsep 14mm
\topskip 0mm
\textheight 238mm
\footskip 14mm
\multicolsep4ex plus2ex minus1ex
\columnsep2em
\columnseprule.4pt

\newcounter{listi}
\newcommand{\stdli}{ \topsep0ex \partopsep0ex % .5ex plus.25ex minus.125ex%
    \parsep.2ex plus.1ex minus.1ex \itemsep0ex% .5ex plus.25ex minus.125ex%
    \leftmargin2.5em \labelwidth2em \labelsep.5em \rightmargin0em}% \samepage }
\newenvironment{arab}{\begin{list}{\textup{(\arabic{listi})}}%
    {\usecounter{listi}\stdli}}{\end{list}}
\newenvironment{rome}{\begin{list}{\textup{(\roman{listi})}}%
    {\usecounter{listi}\stdli}}{\end{list}}
\newenvironment{latin}{\begin{list}{\textup{(\alph{listi})}}%
    {\usecounter{listi}\stdli}}{\end{list}}
\renewenvironment{itemize}{\begin{list}{{$\bullet$}}{\stdli}}{\end{list}}
\newenvironment{myverb}{\pagebreak[2]\begin{small}}{\end{small}\pagebreak[2]}

\newcommand{\ie}{i.e.}
\newcommand{\seq}{\subseteq}
\newcommand{\nn}{\mathbb{N}}
\newcommand{\qq}{\mathbb{Q}}
\newcommand{\rr}{\mathbb{R}}
\newcommand{\zz}{\mathbb{Z}}
\let\ZZ=\zz
\newcommand{\aA}{\mathbb{A}}
\newcommand{\ee}{\mathbb{E}}
\newcommand{\crr}{\mathcal{R}}
\newcommand{\Imp}{\Longrightarrow}
\newcommand{\prep}{\pagebreak[2]\small}
\newcommand{\al}{\alpha}
\newcommand{\La}{\Lambda}
\newcommand{\si}{\sigma}
\newcommand{\Si}{\Sigma}
\renewcommand{\phi}{\varphi}
\renewcommand{\mit}{\:|\:}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\intr}{int}
\DeclareMathOperator{\gp}{gp}
\DeclareMathOperator{\rank}{rank}

\newcommand\pre{2ex plus .2ex minus .2ex}
\newcommand\post{1ex plus .1ex minus .1ex}
\newtheoremstyle{updp}{\pre}{\post}{\upshape}{}{\itshape}{:}{.5em}{}
\theoremstyle{updp}
\newtheorem*{Pf}{Proof}
\newenvironment{pf}{\begin{Pf}}{\qed\end{Pf}}
\newtheorem*{genass}{General assumption}
\newtheoremstyle{itdp}{\pre}{\post}{\itshape\samepage}{}{\bfseries}{:}{.5em}{}
\theoremstyle{itdp}
\newtheorem{lem}{Lemma}
\newtheorem{cor}[lem]{Corollary}
\newtheorem{rem}[lem]{Remark}
\newtheorem*{recform}{Recursion formula}

\title{\textsc{Normaliz}\\ Computing normalizations of affine semigroups}
\author{\hbox to 3cm{\hfil Winfried Bruns}\qquad \hbox to 3cm{Robert
Koch\hfil}\\[1cm]
with contributions by\\
\hbox to 3cm{\hfil Witold Jarnicki} \qquad \hbox to 3cm{Matthias
Siemering\hfil}}

\begin{document}

\maketitle
\tableofcontents
\thispagestyle{empty}

\section{Documentation of the program}
\subsection{Objectives}\label{facil}

Our program \textsc{Normaliz} computes
\begin{arab}
\item the normalization (or integral closure) of an affine semigroup or,
in other terms, the Hilbert basis of a rational cone;
\item the support hyperplanes of the cone;
\item the lattice points and
\item the support hyperplanes of an integral polytope;
\item the generators of the integral closure of the Rees algebra of a monomial ideal $I\seq K[X_1,\dots,X_n]$;
\item the generators of the integral closure of $I$;
\item the Hilbert series and Hilbert polynomial of the semigroup in the
homogeneous case.
\end{arab}

For the theory of affine semigroups and the notions of commutative algebra
used in the following we refer the reader to \cite{BH}.

There exists a \textsc{Singular} library \texttt{normaliz.lib} that
makes \textsc{Normaliz} accessible from \textsc{Singular}. Thus
\textsc{Singular} can be used as a comfortable environment for the
work with \textsc{Normaliz}, and, moreover, \textsc{Normaliz} can be
applied directly to objects belonging to the classes of toric rings
and monomial ideals.


\subsection{Numerical aspects and limitations}

There are two versions of our program: \texttt{normaliz} works with
32 bit integers, and \texttt{enormalz} uses integers of arbitrary
precision. As far as we have observed, \texttt{normaliz} is able to
do all heuristic examples. But if you feel that some arithmetical
problem could have arisen, we recommend using \texttt{enormalz}. (It
should, however, be clear that this version is significantly
slower.)

\emph{Nevertheless there is a common limitation for both versions:}
If you wish
to compute the Hilbert series and polynomial along with the generators of
the semigroup, \texttt{normaliz} and \texttt{enormalz} will only work in
dimension $\le32$.

\subsection{Distribution}

We distribute our program \textsc{Normaliz} through the file \texttt{normaliz.zip}
which can be found in the directory
\[{\texttt{ftp://ftp.mathematik.Uni-Osnabrueck.DE/pub/osm/kommalg/software/}}\]
on our FTP server. You can log in as \texttt{anonymous}.

Download the file \texttt{normaliz.zip} to a directory of your choice and
unzip it by \textsc{InfoZip}'s \texttt{unzip} (or \textsc{PkUnzip} or
\textsc{WinZip} (take care of
the option ``create subdirectories'')). The names of the
subdirectories created are self-explanatory. Nevertheless, some
comments may be useful.

Executables for Win32, Sparc (Solaris), Linux (Redhat) and Mac are
provided separately. The names of the \texttt{zip} files are
self-explanatory.

\subsubsection{\texttt{source/}}

Here you find the $14$ source files (and a {\tt Makefile}):
\begin{center}
\ttfamily
alloc.c\quad elemdiv.c\quad enormalz.cc\quad error.c\quad heap.c \quad hilbert.c\quad hilbert.h\\
homog.c\quad invest.c\quad linequ.c\quad normaliz.cc\quad
reduce.c\quad shorten.c\quad sigma.c
\end{center}



\subsubsection{\texttt{doc/}}

This contains the \LaTeXe\ documentation file \texttt{normaliz.tex},
the compiled version \texttt{normaliz.pdf} and a \texttt{Makefile}.

\subsubsection{\texttt{example/}}

Here are the input and output files of 8 examples, called \texttt{rproj2},
\texttt{rafa1409}, \texttt{squaref0}, \texttt{squaref1}, \texttt{rafa2310},
\texttt{rafa2416}, \texttt{polytop} and \texttt{rees}. We thank Rafael
Villarreal, who sent us some of these examples.

\subsubsection{\texttt{Singular/}}

It contains the \textsc{Singular} library \texttt{normaliz.lib} and
the documentation files \verb+nmz_sing.tex+ and \verb+nmz_sing.pdf+.

\subsection{Compilation}

A \emph{Makefile} is provided with the source code of \textsc{Normaliz}.
The \texttt{enormalz} binary is built simply by entering the command
\begin{center}
\texttt{make}
\end{center}
whereas the \texttt{normaliz} binary is built by specifying the target
through
\begin{center}
\texttt{make normaliz}.
\end{center}
Note that it is crucial to have two libraries  installed to link the
enormalz binary properly. We use the \texttt{NTL}
library\footnote{\url{http://www.shoup.net/ntl}} as a \texttt{C++}
interface for the \texttt{GMP}
library\footnote{\url{http://www.swox.com/gmp/}} which provides thee
long integer arithmetic for \texttt{enormalz}. (The corresponding
variables in the Makefile may have to be customized to your library
directory.)

Via the makefile the source code compiles under \texttt{Unix},
\texttt{Windows/Cygwin}, \texttt{Linux/Redhat} and
\texttt{Macintosh} (provided that the used compiler is compatible
with the widespread \texttt{GCC}).

However, for \texttt{Windows} user we recommend the \texttt{DJGPP}
compiler. It produces much more efficient code. Since we provide
executables for \texttt{Windows}, we omit the details of using
\texttt{DJGPP}.

\subsection{Executables}

Executables for various platforms are provided separately in the
\texttt{ftp} folder.

\subsection{Running the program}

The program \texttt{normaliz} is started by the following command line:
\[\texttt{normaliz [-acfhv] <filename>}\]

It expects its input in the file \texttt{<filename>.in} and writes its
output into \texttt{<filename>.out}. Therefore the argument \texttt{<filename>}
in your command line must \emph{not} contain the suffix \texttt{.in}.

With the option \texttt{-f}, not only the standard output file
\texttt{<filename>.out} will be written, but also several other
files. (See Section~\ref{output} for details.)

With the option \texttt{-a}, all potentially useful output files
will be written (See Section~\ref{output} for details.) The
\texttt{-a} option includes \texttt{-f}.

If you include the option \texttt{-h} in your command line, the $h$-vector and
the (coefficients of the) Hilbert polynomial will be written into
\texttt{<filename>.out}. But note that this will only work if the semigroup
is homogeneous. (See Section~\ref{homog1} for a definition.)

The \texttt{-v} option overrides the \texttt{-h} option
and restricts \texttt{normaliz} to those computations which
determine the multiplicity. The name has been chosen
since this option is particularly interesting for polytopal
applications (see the ``mode = 2'' case below) if one is only
interested in effectively computing the volume of a lattice polytope.
% Upon finishing, the respective value is also written to the command window.

Finally, let us explain the \texttt{-c} option. This will give you
some access to `control' data during the computation. It is designed
for users who run complex examples and wish to see how far
\texttt{normaliz} has come (and if it is still running at all). In
the first part of the computation the information is given as
$$
\texttt{Done with generator}\ n
$$
where $n$ runs from $\rank S+1$ to the number of generators of $S$.
($S$ is the semigroup whose integral closure is to be computed; it
depends on the mode; see below.)

In the second part of the computation the information is given in
the format
\[ \texttt{[<{\it block}>.<{\it subblock}>] <{\it current number}> /
<{\it total number}>} \]
and refers to the triangulation discussed below. The triangulation is
partitioned into blocks and subblocks, and the first two counters refer
to these, whereas \emph{current number} and \emph{total number} describe
the position within the current subblock. (See Section~\ref{triang}
and the final remark at the end of the paper for more information.)

\subsubsection{The input file}\label{input}

The input file \texttt{<filename>.in} is structured as follows.

The first line contains the number of generators of the semigroup $S$
(or the number of lattice points spanning the polytope, or the number of
generators of the ideal $I$ defining the Rees algebra).

The second line contains the dimension of the ambient lattice.

The next lines contain the generators of $S$ (or the spanning
lattice points, or the exponent vectors of the monomials generating
the ideal $I$, respectively), as shown in the examples below.

The last line contains a single digit, called \emph{mode}, namely:

\begin{itemize}
\item[0,] if the program should compute the integral closure of $S$ in the
ambient lattice (the Hilbert basis of the cone spanned by the generators of
$S$);
\item[1,] if the normalization of $S$ is to be computed (\ie\ the integral
closure in the sublattice generated by $S$);
\item[2,] if the integral points in a polytope and its Ehrhart semigroup are to be computed;
\item[3,] if the integral closure of the Rees algebra of $I$ is to be computed.
\end{itemize}

\subsubsection{The lattices}

The output of \textsc{Normaliz} depends on the lattices involved.
Therefore we define the \emph{ambient lattice} $\aA$, the semigroup
$S$ and the \emph{effective lattice} $\ee$ as follows:
\begin{itemize}
\item[mode 0:] $\aA=\zz^n$ where $n$ is the number contained in the second line of
the input file;

$S$ is the subsemigroup of $\aA$ generated by the vectors in the
input file;

$\ee$ is the smallest direct summand of $\aA$ containing the
subgroup $\gp(S)\subset\aA$ generated by $S$.

\item[mode 1:] $\aA$ and $S$ as for mode 0, but $\ee=\gp(S)$.
\item[mode 2 (polytopal application):] $\aA=\zz^{n+1}$;

$S$ is generated by the vectors $(x,1)$ for the vectors $x$ in the
input file;

$\ee$ now defined as for mode 0.

\item[mode 3 (Rees application):] $\aA=\zz^{n+1}$;

$S$ is generated by the unit vectors $e_1,\dots,e_n$ (representing
the indeterminates of the polynomial ring) and the vectors $(x,1)$
for the vectors $x$ in the input file;

$\ee=\zz^{n+1}$.

\end{itemize}

In each case the integral closure of $S$ in $\ee$ is computed. See also Subsection \ref{intro}.


\subsubsection{The output file(s)}\label{output}

In the case ``mode $\le1$'' the output file \texttt{<filename>.out} contains
the following data:
\begin{itemize}
\item the generators of the integral closure of $S$ in $\ee$;
\item if $\rank \ee=\rank \aA$, the extreme rays of the cone $C$ generated by $S$
and the (unique) support hyperplanes of $C$;
\item $\rank \gp(S)$;
\item the index of $\gp(S)$ in $\ee$ in mode 0 (in mode 1 it is 1 by default);
\item if $S$ is homogeneous (see below), you will
find its multiplicity in the output file, too;
\item if, in addition, you have used the option \texttt{-h}, there are
also the $h$-vector and the coefficients of the Hilbert polynomial.
\end{itemize}

Note that the support hyperplanes are not listed if $\rank \ee<\rank
\aA$. However, in this case a description of the cone generated by
$S$ in $\rr\ee$ is available if the option \texttt{-a} is used (see
below).

\label{homog1}
We call $S$ \emph{homogeneous} if there is an integer-valued linear form
$\phi$ on $\ee$  such that all the generators $v$ of $S$ given in the input
file satisfy $\phi(v)=1$. For instance, the examples \texttt{rafa2416},
\texttt{squaref1} and \texttt{rproj2} from the directory \texttt{example}
are homogeneous.

Recall that the option \texttt{-v} suppresses the computation of the
Hilbert basis and therefore restricts the output to rank, index,
support hyperplanes, and multiplicity. Thus it may happen that,
using \texttt{-v}, the output file becomes completely empty! In the
modes $\ge2$, this option behaves accordingly. It was introduced for
users who wish to efficiently determine only the (normalized) volume
of a lattice polytope. This application will be discussed now.

The extreme rays are given by the elements in $S$ that define the
extreme rays. Therefore these vectors need not have coprime entries.

\textbf{Attention.} \texttt{normaliz} uses 32 bit arithmetic for all
its computation, including Hilbert functions. It can very well
happen, that the computation of the integral closure of $S$ runs
without problems, but an overflow occurs in the Hilbert function
computation. In this case you must resort to \texttt{enormalz}.

A good test for the $h$-vector is whether its entries are
nonnegative and sum up to the multiplicity. \emph{To get a correct
denominator for the Hilbert polynomial with} \texttt{normaliz},
\emph{one needs $\rank S\le 13$.} If this condition is not
fulfilled, \texttt{normaliz} does not compute the Hilbert
polynomial.

If ``mode $=2$'', the following data can be found in the output file:
\begin{itemize}
\item the generators of the semigroup determined by the polytope,
called Ehrhart semigroup in the following;
\item the lattice points of the polytope;
\item its normalized volume;
\item its extreme points and its support hyperplanes if it is of full dimension;
\item if you have put the option \texttt{-h}, there are
also the $h$-vector and the coefficients of the Ehrhart polynomial.
\end{itemize}

In ``mode $=3$'', the output file contains the following:
\begin{itemize}
\item the generators of the integral closure $\Bar{\crr}$ of the Rees algebra;
\item the generators of the integral closure of the ideal;
\item the extreme rays and the support hyperplanes;
\item the multiplicity of the semigroup if it is homogeneous;
\item if the ideal is primary to the irrelevant maximal ideal, the multiplicity
of the ideal (not to be confused with the multiplicity of the
semigroup);
\item if, in addition, the \texttt{-h} option has been used, the $h$-vector
and the coefficients of the Hilbert polynomial of $\Bar{\crr}$ are computed,
too.
\end{itemize}

\subsubsection{The \texttt{-f} and \texttt{-a} options}

With the \texttt{-f} or \texttt{-a} option in the command line,
\textsc{Normaliz} writes additional output files whose names are of
type \texttt{<filename>.<type>}. In the following we denote the
files simply by their types. Note that \texttt{-a} includes
\texttt{-f}.

With the \texttt{-f} option the following files are written,
provided the information that should go into them is available:

\begin{itemize}
\item[\texttt{gen}] The generators of the integral closure are written to the file
\texttt{out} (provided they have been computed). The format of this
file and the other files (with the exception of \texttt{inv}) is
completely analogous to that of the input file, except that there is
no last line denoting the mode.

\item[\texttt{sup,val}] If $\rank \aA=\rank \ee$, then the support hyperplanes are
written to \texttt{sup}. In this case, the support hyperplanes of
the cone $C$ are evaluated (as linear forms) on the generators, too.
The resulting matrix, with the generators corresponding to the rows
and the support hyperplanes corresponding to the columns, is written
to the file \texttt{val}.

\item[\texttt{inv}] The file \texttt{inv} contains all the information from the
file \texttt{out} that is not contained in any of the other files.
It helps to import these data into \texttt{Singular}.

\end{itemize}

With the \texttt{-a} option the following additional files are
written, provided certain conditions are satisfied and the
information that should go into them is available:

\begin{itemize}

\item[\texttt{ext}] The file \texttt{ext} contains the extreme rays
(or points in polytopal mode), provided they have been computed.

\item[\texttt{egn,esp,evl}] If $\rank \ee<\rank \aA$ or the mode is
$1$, there are corresponding files \texttt{egn}, \texttt{esp} and
\texttt{evl}. These are defined as \texttt{gen}, \texttt{sup} and
\texttt{val}, however with respect to the lattice $\ee$ and a basis
of $\ee$.

Note that these data provide a description of the integral closure
of $S$ in the form $\ee\cap C$.

\item[\texttt{tri}] The file \texttt{tri} contains the triangulation of the cone
$C$  computed by \textsc{Normaliz}.

The first line contains the number of simplicial cones in the
triangulation, and the next line contains the number $m+1$ where
$m=\rank \ee$. Each of the following lines specifies a simplicial
cone $\Delta$: the first $m$ numbers are the indices (with respect
to the order in the input file) of those generators of $S$ that span
$\Delta$, and the last entry is the multiplicity of $\Delta$ in
$\ee$, i.~e.\ the absolute value of the determinant of the matrix of
the spanning vectors (as elements of $\ee$).


\end{itemize}


\subsubsection{Examples}

The file \texttt{rproj2.in} contains the following:

\begin{multicols}{2}
\begin{myverb}
\begin{verbatim}
16
7
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
1 1 1 0 0 0 1
1 1 0 1 0 0 1
1 0 1 0 1 0 1
1 0 0 1 0 1 1
1 0 0 0 1 1 1
0 1 1 0 0 1 1
0 1 0 1 1 0 1
0 1 0 0 1 1 1
0 0 1 1 1 0 1
0 0 1 1 0 1 1
0
\end{verbatim}
\end{myverb}
\end{multicols}

This means that we wish to compute the integral closure of the semigroup
generated by the $16$ vectors
\[ [1,0,0,0,0,0,0]\,,\quad [0,1,0,0,0,0,0]\,,\quad \dots\,,\quad
[0,0,1,1,0,1,1] \]
in dimension $7$. We compute it in the ambient lattice
$\zz^7$, which is indicated by the final digit $0$.

Calling \textsc{Normaliz} by the command
\[ \texttt{normaliz rproj2} \]
produces the file \texttt{rproj2.out} which has the following content:

\begin{multicols}{2}
\begin{myverb}
\begin{verbatim}
17 generators of integral closure:
  1  0  0  0  0  0  0
  0  1  0  0  0  0  0
  0  0  1  0  0  0  0
  0  0  0  1  0  0  0
  0  0  0  0  1  0  0
  0  0  0  0  0  1  0
  1  1  1  0  0  0  1
  1  1  0  1  0  0  1
  1  0  1  0  1  0  1
  1  0  0  1  0  1  1
  1  0  0  0  1  1  1
  0  1  1  0  0  1  1
  0  1  0  1  1  0  1
  0  1  0  0  1  1  1
  0  0  1  1  1  0  1
  0  0  1  1  0  1  1
  1  1  1  1  1  1  2

16 extreme rays:
  1  1  1  0  0  0  1
  1  1  0  1  0  0  1
  1  0  1  0  1  0  1
  1  0  0  1  0  1  1
  1  0  0  0  1  1  1
  0  1  1  0  0  1  1
  0  1  0  1  1  0  1
  0  1  0  0  1  1  1
  0  0  1  1  1  0  1
  0  0  1  1  0  1  1
  1  0  0  0  0  0  0
  0  1  0  0  0  0  0
  0  0  1  0  0  0  0
  0  0  0  1  0  0  0
  0  0  0  0  1  0  0
  0  0  0  0  0  1  0

(original) semigroup has rank 7 (maximal)
(original) semigroup is of index 1

24 support hyperplanes:
   1   1   1   1   1   0  -2
   1   1   0   1   1   1  -2
   1   1   1   0   1   1  -2
   0   1   1   0   0   1  -1
   0   0   0   0   0   1   0
   1   0   0   1   0   1  -1
   1   0   1   1   1   1  -2
   1   1   1   0   0   0  -1
   1   1   0   1   0   0  -1
   1   0   1   0   1   0  -1
   0   0   0   0   1   0   0
   0   1   0   1   1   0  -1
   1   0   0   0   0   0   0
   1   1   1   1   1   1  -3
   1   0   0   0   1   1  -1
   0   1   0   0   1   1  -1
   0   1   0   0   0   0   0
   1   1   1   1   0   1  -2
   0   0   1   1   1   0  -1
   0   0   0   1   0   0   0
   0   0   1   1   0   1  -1
   0   0   1   0   0   0   0
   0   1   1   1   1   1  -2
   0   0   0   0   0   0   1

(original) semigroup is homogeneous via the linear form
   1   1   1   1   1   1   -2

multiplicity = 72
\end{verbatim}
\end{myverb}
\end{multicols}

From this, we see that there are $17$ generators of the integral closure
of the semigroup in $\zz^7$ and $16$ extreme rays, that the semigroup has index $1$ in $\zz^7$,
and that the corresponding support hyperplanes are given by the linear forms
$[1,1,1,1,1,0,-2]$, $[1,1,0,1,1,1,-2]$, \dots, $[0,0,0,0,0,0,1]$.
Moreover, we are given the information that the semigroup is homogeneous
and that its multiplicity is $72$.

If we use the same input file \texttt{rproj2.in} and call \texttt{normaliz}
with the option \texttt{-h}, \texttt{rproj2.out} will contain the additional
lines

\begin{myverb}
\begin{verbatim}
h-vector =  1  9  31  25  6  0  0

Hilbert poly :  1  97/30  71/15  49/12  13/6  41/60  1/10
\end{verbatim}
\end{myverb}

which state that the $h$-vector of $\Bar{S}$ is
\[ (h_0,h_1,\dots,h_6)=(1,9,31,25,6,0,0)\,, \]
and that the Hilbert polynomial of $\Bar{S}$ is given by
\[ P_{\Bar{S}}(t)=1+\frac{97}{30}t+\frac{71}{15}t^2+\frac{49}{12}t^3
+\frac{13}{6}t^4+\frac{41}{60}t^5+\frac{1}{10}t^6\,. \]

Here is another example from the file \texttt{polytop.in}:

\begin{myverb}
\begin{verbatim}
4
3
0 0 0
2 0 0
0 3 0
0 0 5
2
\end{verbatim}
\end{myverb}

Here the lattice points of the integral polytope with the $4$ vertices
\[ [0,0,0]\,,\quad [2,0,0]\,,\quad [0,3,0]\quad\text{ and }\quad [0,0,5] \]
in $\rr^3$ are to be computed. (Note the last line, indicating the
polytopal mode $2$.)

The command \texttt{normaliz polytop} produces the file \texttt{polytop.out}:

\begin{multicols}{2}
\begin{myverb}
\begin{verbatim}
19 generators of Ehrhart ring:
  0  0  0  1
  2  0  0  1
  0  3  0  1
  0  0  5  1
  1  2  4  2
  0  1  3  1
  1  0  2  1
  0  2  1  1
  1  1  0  1
  0  0  4  1
  0  1  2  1
  1  0  1  1
  0  2  0  1
  0  0  3  1
  0  1  1  1
  1  0  0  1
  0  0  2  1
  0  1  0  1
  0  0  1  1

18 lattice points in polytope:
  0  0  0
  2  0  0
  0  3  0
  0  0  5
  0  1  3
  1  0  2
  0  2  1
  1  1  0
  0  0  4
  0  1  2
  1  0  1
  0  2  0
  0  0  3
  0  1  1
  1  0  0
  0  0  2
  0  1  0
  0  0  1

4 extreme points of polytope:
  0  0  0
  2  0  0
  0  3  0
  0  0  5

4 support hyperplanes:
    0    0    1   >=    0
    0    1    0   >=    0
    1    0    0   >=    0
  -15  -10   -6   >=  -30

normalized volume = 30

\end{verbatim}
\end{myverb}
\end{multicols}

The desired lattice points are the $18$ ones listed above. To complete the
picture, we also provide all the generators of the Ehrhart ring of the
polytope.
(There are $19$ of them in this example.) Furthermore, the original polytope
is the solution of the system of the $4$ inequalities
\[ x_3\ge0\,,\quad x_2\ge0\,,\quad x_1\ge0\quad\text{ and }\quad 15x_1+10x_2+6x_3\le30\,, \]
and has normalized volume $30$.

Again, calling \textsc{Normaliz} via the command
\texttt{normaliz -h polytop} produces
additional output in \texttt{polytop.out}, namely

\begin{myverb}
\begin{verbatim}
h-vector =  1  14  15  0

Ehrhart poly :  1  4  8  5
\end{verbatim}
\end{myverb}

This provides the information that the $h$-vector of the Ehrhart ring is
\[ (h_0,h_1,h_2,h_3)=(1,14,15,0)\,, \]
and its Ehrhart polynomial is
\[ P(t)=1+4t+8t^2+5t^3\,. \]

To complete the picture, let us discuss the example in \texttt{rees.in}:
\begin{myverb}
\begin{verbatim}
10
6
1 1 1 0 0 0
1 1 0 1 0 0
1 0 1 0 1 0
1 0 0 1 0 1
1 0 0 0 1 1
0 1 1 0 0 1
0 1 0 1 1 0
0 1 0 0 1 1
0 0 1 1 1 0
0 0 1 1 0 1
3
\end{verbatim}
\end{myverb}

Comparing with the data in \texttt{rproj2.in} shows that \texttt{rees}
is the origin of \texttt{rproj2}. (For details see the comments on the
reduction of item (3) on page \pageref{item3}.)

Here we want to compute the integral closure of the Rees algebra of
the ideal generated by the monomials corresponding to the above $10$
exponent vectors. (Note again the last line, containing $3$ in this
case.) The output in \texttt{rees.out} coincides with that in
\texttt{rproj2.out}, up to notions and the supplementary information
on the integral closure of the ideal:

\begin{myverb}
\begin{verbatim}
10 generators of integral closure of the ideal:
  1  1  1  0  0  0
  1  1  0  1  0  0
  1  0  1  0  1  0
  1  0  0  1  0  1
  1  0  0  0  1  1
  0  1  1  0  0  1
  0  1  0  1  1  0
  0  1  0  0  1  1
  0  0  1  1  1  0
  0  0  1  1  0  1
\end{verbatim}
\end{myverb}

A brief look at \texttt{rproj2.out} shows that exactly the
generators with the last coordinate $1$ have been extracted. (So the
ideal is integrally closed. This is not surprising because we have
chosen squarefree monomials.)


\subsection{Copyright}

You can use this program freely, provided that you refer to it in the
following manner in any publication for which it has been used:
\begin{center}
W. Bruns, R. Koch et al.: \textsc{Normaliz}, computing normalizations\\% \hskip3em
of affine semigroups. Available via anonymous ftp from\\[.5ex]
\texttt{ftp://ftp.mathematik.uni-osnabrueck.de/pub/osm/kommalg/software/}
\end{center}

\section{Algorithmic and mathematical background}
\subsection{Introduction}\label{intro}

As can be seen from Section~\ref{facil}, we are faced with the following
situation.

Given a finite set
\[ E\seq\zz^n\,, \]
consider the \emph{affine semigroup}
\[ S=S(E)=\nn\cdot E=\sum_{v\in E}\nn\cdot v \]
generated by $E$, and its \emph{integral closure}
\[ \Bar{S}_{\zz^n} = \{x\in\zz^n\mit\text{$x$ integral over $S$}\}
= \{x\in\zz^n\mit k\cdot x\in S \text{ for some } k\ge 1\} \]
in $\zz^n$, or its \emph{normalization}
\[ \Bar{S}_{\zz E}=\{x\in\zz E\mit \text{$x$ integral over $S$}\} \]
(integral closure in $\zz E$).

Now let
\[ C=\cone(E)=\rr_{\ge0}\cdot E=\sum_{v\in E}\rr_{\ge0}\cdot v\,. \]
The importance of the cone $C$ becomes clear from the following
\begin{rem}\label{fingen}
\begin{rome}
\item $\Bar{S}_L=C\cap L$ for $L=\zz^n,\zz E$.
\item $\Bar{S}_L$ is a finitely generated semigroup.
\end{rome}
\end{rem}

\begin{genass}
In the following, we always assume that $C$ is a strictly convex cone,
\ie\ $C$ does not contain any nontrivial linear subspace,
\ie\ for all $x\in C$ we have:
\[ -x\in C\quad\Imp\quad x=0\,. \]
\end{genass}

Under this assumption, we call an element $v\in \Bar{S}_L$
\emph{irreducible} if a decomposition
\[ v=v_1+v_2 \quad \text{with $v_i\in \Bar{S}_L$} \]
implies $v_1=0$ or $v_2=0$.

As you may recall, \textsc{Normaliz} is able to compute (compare with the
four ``modes'')
\begin{arab}
\item[(0)] the integral closure of an affine semigroup in $\zz^n$;
\item[(1)] the normalization of an affine semigroup;
\item[(2)] the lattice points of an integral polytope and its Ehrhart ring;
\item[(3)] the integral closure of a monomial ideal $I\seq K[X_1,\dots,X_n]$
and the integral closure of its Rees algebra;\label{item3}
\item[(H)] the Hilbert series and Hilbert polynomial.
\end{arab}

Obviously, (1) can be reduced to (0) by performing a suitable change
of coordinates (in order to pass to the effective lattice $\ee$). As
for (2), let $v_1,\dots,v_m\in\zz^n$ be the vertices of the
polytope. The lattice points in the polytope are exactly the vectors
$v\in\zz^n$ such that $[v,1]\in\Bar{S}_{\zz^{n+1}}$, where $S$ is
generated by $[v_1,1],\dots,[v_m,1]\in\zz^{n+1}$. This is how to
reduce (2) to (0).

In order to solve (3), one starts as in (2). In fact this realizes the
multiplication of the generators of $I$ by an additional indeterminate.
Furthermore, one adds the generators
\[ [1,0,\dots,0,0]\,,\dots\,,\,[0,\dots,0,1,0]\in\zz^{n+1} \]
representing the indeterminates $X_1,\dots,X_n$, and again arrives at (0).

Therefore only the following two problems have to be solved.
\begin{rome}
\item[(G)] Find an irreducible system of generators of $\Bar{S}_L$.
\item[(H)] Calculate the Hilbert series (and the Hilbert polynomial)
of $\Bar{S}_L$.
\end{rome}

In order to solve problem (G), one proceeds according to the following
steps:

\begin{rome}
\item[(G1)] Perform a change of coordinates (if necessary), such that
$L=\zz^n$ and $\dim(C)=n$.
\item[(G2)] Decompose
\begin{equation}\label{decomp}
C=\Si_1\cup\cdots\cup\Si_t
\end{equation}
into \emph{simplicial cones} $\Si_j\seq\rr^n$ (\ie\ $\Si_j$ is spanned
by exactly $n$ linearly independent vectors). This process is called \emph{triangulation}.
\item[(G3)] Solve problem (G) for each $\Si_j$.
\item[(G4)] Collect and reduce the generators found in step (G3).
\end{rome}

Steps (G2)--(G4) will be discussed in the following three sections,
and problem (H) is dealt with in Section~\ref{hilb}. (You can immediately
proceed to Section~\ref{hilb} if you are especially interested in
problem (H).)

\subsection{Constructing the triangulation}\label{triang}

The triangulation is constructed inductively.
The inductive step can be carried out as follows.
Assume that
$v_1,\dots,v_s\in\zz^n$ span a cone $C_0$ with decomposition
\[ C_0=\Si_1\cup\cdots\cup\Si_r\,, \]
and $v_1,\dots,v_s,v_{s+1}\in\zz^n$ span a cone $C_1$.
In order to decompose $C_1$, we proceed in four steps:

\begin{latin}
\item Find all support hyperplanes $h_1,\dots,h_k$ of $C_0$ for which $v_{s+1}$
lies in the negative half-space.
(Actually, the computations of the support hyperplanes
and the decomposition of $C_0$ are carried out simultaneously.
For details of the former we refer the reader to \cite{Bu}.)
\item Find all pairs $(h_i,\Si_j)$ such that $h_i$ is a support hyperplane
of $\Si_j$.
\item For each pair $(h_i,\Si_j)$ determined in (b), build a new simplicial
cone from the vectors $v_{s+1}$ and
$h_i\cap\Si_j\cap\{v_1,\dots,v_s\}$. (Note that the last set will consist of
exactly $n-1$ vectors.)
\item All the simplicial cones found in (c), together with $\Si_1,\dots,\Si_r$,
will provide a decomposition of $C_1$.
\end{latin}

For purposes of efficiency, especially when the Hilbert series is to be
computed (and the \texttt{-h} option is active), we subdivide the
triangulation into \emph{blocks} and \emph{subblocks}.
Every block consists of exactly those simplicial cones found in step (c) above.
That is, whenever a new vector $v_{s+1}$ has to be integrated, a new block
starts and collects all simplicial cones which are constructed due to $v_{s+1}$
(and which in particular contain $v_{s+1}$).
$v_{s+1}$ is then called the \emph{characteristic vector} of the block.
A similar, but slightly more difficult operation leads to subblocks
within the blocks.

\subsection{The simplicial case}\label{simpl}

Once having computed a complete triangulation as described above, one is
faced with the simplicial case. Therefore let
$v_1,\dots,v_n\in\zz^n$ span a simplicial cone
\[ \Si=\sum_{i=1}^n \rr_{\ge0}\cdot v_i\seq\rr^n \,. \]
How can one calculate generators of the semigroup
\[ G:=\Si\cap\zz^n\,? \]

Clearly, $v_1,\dots,v_n$ and the set
\begin{equation}\label{B}
B:=\{\al_1v_1+\dots+\al_nv_n\in\zz^n\mit \al_i\in\qq\,,\,0\le\al_i<1\}
\end{equation}
generate the semigroup $G$.
Therefore the main step is to explicitly determine set $B$.

To do this, define the lattice
\begin{equation}\label{La}
\La:=\zz v_1+\dots+\zz v_n\,,
\end{equation}
and observe that there is a bijection
\[ B\stackrel{\text{1:1}}{\longleftrightarrow}\zz^n/\La:\quad b\mapsto b+\La
\,, \]
so that we have to find those representatives of the residue classes that lie
in $B$. This is achieved as follows.

By elementary row and column operations, one finds matrices $T_r,T_c\in
\GL_n(\zz)$ such that
\[ T_r\cdot(v_1,\dots,v_n)\cdot T_c=\diag(d_1,\dots,d_n) \]
is a diagonal matrix with strictly positive entries $d_i>0$.
Now $\La$ is spanned by the columns of
$(v_1,\dots,v_n)\cdot T_c$, \ie\ by the columns of $T_r^{-1}\cdot
\diag(d_1,\dots,d_n)$.

Let $T_r^{-1}=(w_1,\dots,w_n)$. This implies
\[ \La=\zz d_1w_1+\dots+\zz d_nw_n\,, \]
hence
\[ B=\{\al_iw_i\!\!\!\!\mod\La\mit i=1,\dots,n\,,\, \al_i=0,\dots,d_i-1\}\,. \]

\subsection{Collecting generators}\label{coll}

For a decomposition \eqref{decomp} of the original cone $C$, step (G3) yields
a set $U_j$ of generators of $\Si_j\cap\zz^n$ for every $\Si_j$.
If we put
\[ U=\bigcup_{j=1}^t U_j\,, \]
then the elements of $U$ obviously generate $C\cap\zz^n$.
Now it remains to construct a subset $V\seq U$ whose elements are irreducible
\emph{and} still generate $C\cap\zz^n$.

Let $U=\{u_1,\dots,u_N\}$. Set $V$ is constructed
inductively. In the $0$-th step, we put $V=\emptyset$. In the $k$-th step,
we check if $u_k-u\in C$ for some $u\in V$. If so, we forget $u_k$ and
increase $k$ by $1$. If not, we remove all those $u$ from $V$ which satisfy
$u-u_k\in C$, and add $u_k$ to $V$ before increasing $k$ by $1$.

To test whether a vector $v\in\zz^n$ lies in $C$, one evaluates the support
hyperplanes in $v$.

\subsection{Computing the Hilbert series}\label{hilb}

Let us recall and extend the notation from Section~\ref{intro},
where we start with a finite set $E=\{w_1,\dots,w_m\}
\linebreak[0]\seq\zz^n$.
The integral closure of the affine semigroup $S=S(E)\seq\zz^n$
is denoted by $\Bar{S}\seq\zz^n$. We may assume that the cone $C=\cone(E)$
satisfies $\dim(C)=n$.

Next we define the corresponding semigroup rings
\[ R:=K[X^v\mit v\in S]\quad\text{and}\quad \Bar{R}:=K[X^v\mit v\in\Bar{S}]\,.
\]
(Here, of course, $K$ is a field, and $X$ is the $n$-tuple $(X_1,\dots,X_n)$
of indeterminates.)
By Remark~\ref{fingen} (ii), $\Bar{R}$ is a finite $R$-module.

Of special interest is the \emph{homogeneous}\label{homog2}
situation, \ie\ there is $\phi\in\Hom(\zz^n,\zz)$ such that $\phi(w_i)=1$
for all $i$. Then there is a natural grading of $\Bar{R}$, given by
\[ \deg X^v:=\phi(v)\,, \]
and so $R$ is generated in degree $1$.

\emph{Throughout this section, we will assume that $\boldsymbol{R}$ is
homogeneous.}
Then, according to the grading, write
\[ \Bar{R}=\bigoplus_{k=0}^\infty \Bar{R}_k\,. \]
(Once more we refer the reader to \cite{BH}.) As is generally known,
the \emph{Hilbert function} of $\Bar{R}$ is defined by
\[ H(\Bar{R},k)=\dim_K(\Bar{R}_k)\quad\text{for $k\ge0$} \]
and coincides with the \emph{Hilbert polynomial} $P_{\Bar{R}}$ for large
values of $k$:
\[ H(\Bar{R},k)=P_{\Bar{R}}(k)\quad\text{for $k\gg0$}\,. \]
The \emph{Hilbert series} of $\Bar{R}$ is
\[ H_{\Bar{R}}(t)=\sum_{k=0}^\infty H(\Bar{R},k)t^k\,. \]
and can be written as
\[ H_{\Bar{R}}(t)=\frac{h_0+h_1t+\dots+h_{n-1}t^{n-1}}{(1-t)^n}\,, \]
where $(h_0,h_1,\dots,h_{n-1})$ is the $\boldsymbol{h}$\emph{-vector} of
$\Bar{R}$. In particular,
\[ H(\Bar{R},k)=P_{\Bar{R}}(k)\quad\text{for all $k\ge0$}\,. \]

Before discussing the general case, one should investigate the simplicial case.

\subsubsection{The simplicial case}\label{simplicial}

Let $v_1,\dots,v_n\in\zz^n$ span a simplicial cone $\Si\seq\rr^n$,
and define the semigroup $G:=\Si\cap\zz^n$. Then the corresponding semigroup
rings become
\[ R=K[X^{v_1},\dots,X^{v_n}]\quad\text{and}\quad\Bar{R}=K[X^v\mit v\in G]\,.\]
An important fact is given by the following

\begin{rem}\label{free}
$\Bar{R}$ is free over $R$ with basis $X^B:=\{X^b\mit b\in B\}$, where
$B$ is defined as in \eqref{B}.
\end{rem}

\begin{pf}
Clearly, $X^B$ generates $\Bar{R}$ over $R$.
Now assume that $B=\{b_1,\dots,b_N\}$ and
\[ r_1X^{b_1}+\dots+r_NX^{b_N}=0\quad\text{with $r_i\in R$}\,. \]
As it suffices to look at monomial components, we may assume that
\[ r_i=\text{monomial}=k_iX^{s_{i1}v_1}\dotsm X^{s_{in}v_n}
= k_iX^{s_{i1}v_1+\dots+s_{in}v_n} \]
and
\[ b_i+s_{i1}v_1+\dots+s_{in}v_n=b_j+s_{j1}v_1+\dots+s_{jn}v_n \]
for all $i,j$. But this immediately implies $b_i-b_j\in\La$ (with $\La$
from \eqref{La}), hence $b_i=b_j$.
\end{pf}

Remark~\ref{free} has an immediate consequence.

\begin{cor}\label{practcomp}
We have
\[ H_{\Bar{R}}(t)=\frac{h_0+h_1t+\dots+h_{n-1}t^{n-1}}{(1-t)^n} \]
with the $h$-vector given by $h_i=\#\{b\in B\mit \deg X^b=i\}$.
\end{cor}

\begin{pf}
The remark yields
\[ \Bar{R}=\bigoplus_{b\in B} RX^b\,, \]
hence
\[ H_{\Bar{R}}=\sum_{b\in B} H_{RX^b}\,. \]
Recalling that
\[ H_{RX^b}(t)=\frac{t^{\deg X^b}}{(1-t)^n} \]
finishes the proof.
\end{pf}

\subsubsection{The general case}\label{general}

In order to handle the general case, a combinatorial approach to the
Hilbert function and series is helpful.

For a subset $\emptyset\ne T\seq C=\cone(E)$, define the Hilbert function
of $T$ by
\[ H(T,k):=\#\{v\in T\cap\zz^n\mit\phi(v)=k\}\quad\text{for $k\ge0$}\,, \]
and (formally) the Hilbert series of $T$ by
\[ H_T(t)=\sum_{k=0}^\infty H(T,k)t^k\,. \]
For $T=\emptyset$, we set $H_\emptyset(t)=H(\emptyset,0)=1$.

Next we claim that this definition makes sense, \ie\ $H(T,k)<\infty$ for
all $k\ge0$ and $T\seq C$. The proof is quite simple: It suffices to consider
$H(C,k)$. Now if $w\in C$ satisfies $\phi(w)=k$, then there is a representation
\[ w=\sum_{v\in E} \al_v\cdot v \]
with $\al_v\ge0$ and $k=\phi(w)=\sum_{v\in E}\al_v$. Hence every $\al_v$ is
bounded, and so is every coordinate of $w$. Altogether we have shown that
there is only a finite number of possibilities for the choice of a vector
$w\in C$ satisfying $\phi(w)=k$ and $w\in\zz^n$.

The following remark shows that the Hilbert series $H_T$ of a subset $T\seq C$
generalizes the Hilbert series $H_{\Bar{R}}$ of $\Bar{R}$.

\begin{rem}
We have $H(C,k)=H(\Bar{R},k)$ for all $k\ge0$.
\end{rem}

\begin{pf}
Simply write
\[ \Bar{R}_k=\bigoplus_{\substack{v\in\Bar{S}\\\phi(v)=k}} K\cdot X^v\,. \]
Therefore
\[ H(\Bar{R},k)=\#\{v\in\Bar{S}\mit\phi(v)=k\}=H(C,k) \]
by Remark~\ref{fingen} (i).
\end{pf}

In particular, the Hilbert series of any convex (in particular: simplicial)
subcone $C'\seq C$ coincides, of course, with that of the corresponding
semigroup ring $K[X^v\mit v\in C'\cap\zz^n]$.

Now there is an especially interesting connection between the Hilbert
series of subsets of $C$. We only need the simplicial version.

\begin{lem}\label{intdec}
Let $\Si\seq C$ be the simplicial cone spanned by the vectors $v_1,\dots,v_n\in
\zz^n$. Then
\[ H_{\Si}=\sum_{\si\seq\{v_1,\dots,v_n\}} H_{\intr(\cone(\si))}\,, \]
where $\cone(\si)=\rr_{\ge0}\cdot\si$ is the (possibly lower-dimensional)
cone spanned by the vectors from $\si$, and $\intr(\cone(\si))$ is its
interior (with respect to the standard topology of\/ $\rr^n$\!).
\end{lem}

\begin{pf}
If $v\in \Si\cap\zz^n$ has a representation
\[ v=\sum_{i\in I} \al_iv_i \]
with $\al_i>0$ for all $i\in I$, then
\[ v\in\intr(\cone\{v_i\mit i\in I\})\,, \]
and vice versa. The zero vector is also counted correctly due to the convention
$H_\emptyset=1$.
\end{pf}

Finally, we are now able to discuss the general case.  For this, one uses
the decomposition
\begin{align}
C=\Si_1\cup\cdots\cup\Si_t\tag{\ref{decomp}}
\end{align}
of $C$ into simplicial subcones $\Si_j$ found in step (G2).
One then proceeds by induction. The case $t=1$ is clear from Section%
~\ref{simplicial} and Lemma~\ref{intdec}. The inductive step can be derived
from Lemma~\ref{intdec} (and its proof) and is stated in the following

\begin{recform}
Suppose that
\[ C_1=C_0\cup\Si\,, \]
where $\Si\seq C$ is a simplicial cone spanned by the vectors
$v_1,\dots,v_n\in\zz^n$ (satisfying $\phi(v_i)=1$ for $i=1,\dots,n$),
and $C_0,C_1\seq C$ are finite unions of simplicial
cones. Then, with the notation introduced above,
\begin{equation}\label{rf}
H_{C_1}=H_{C_0}+\sum_{\substack{\si\seq\{v_1,\dots,v_n\}\\
\si\nsubseteq\text{simplicial subcone of $C_0$}}} H_{\intr(\cone(\si))}\,.
\end{equation}
\end{recform}

This is the formula we use in our implementation. However, we do not calculate
$H_{\intr(\cone(\si))}$ directly from the definition, but use the
representation
\[ H_{\intr(\cone(\si))}(t)=\frac{h_1't+\dots+h_{|\si|}'t^{|\si|}}
{(1-t)^{|\si|}}\,, \]
where $|\si|:=\#\si\ge1$ and
\[ h_i' := \#\{b\in B\cap\cone(\si)\mit \phi(b)=|\si|-i\} \]
for $1\le i\le|\si|$ (and $B$ is as in \eqref{B}).

The validity of this approach can be seen from the proofs of Remark~\ref{free}
and Corollary~\ref{practcomp}: One shows that $K[X^v\mit v\in\intr(\cone(\si))
\cap\zz^n]$ is free over $K[X^v\mit v\in\si]$ with basis
$X^{B'}$. Here
\[ B':=\biggl\{\sum_{v_i\in\si} \al_iv_i\in\zz^n\mit \al_i\in\qq\,,\,0<\al_i\le1\biggr\} \]
is in a one-to-one correspondence with $B_\si$ via the bijection
\[ \psi: B_\si\to B': v\mapsto \sum_{v_i\in\si} v_i-v\,. \]
Hence $h_i'$ must equal
\[ \#\{b\in B'\mit \phi(b)=i\}
= \#\{b\in B_\si\mit \phi(b)=|\si|-i\}\,. \]

Some final remarks:
(1) The subdivision of the triangulation into blocks and subblocks
(see Section~\ref{triang}) allows us to simplify the summation in \eqref{rf}:
$\si$ must contain the characteristic vector of the current (sub-)block,
and it must not be a face of any (already accounted) simplex of this
(sub-)block. This reduces the investigation to the current subblock
and speeds up the computation considerably, by a factor of at least $3$.
In order to check whether $\si$ has to be accounted, we also use bit
operations now. This reduces the computation times by another factor
of $5$, resulting in a considerably better performance of the program,
compared to earlier versions.

(2) We only have restricted the computation of the Hilbert series
to the homogeneous case because it is considerably easier to implement
than the general case, in which the denominator of the Hilbert series has
the form $\prod_{i=1}^n (1-t^{a_i})$, and the $a_i$ vary along with the
simplicial subcones.

\begin{thebibliography}{XX}
\markboth{\refname}{\refname}
\bibitem[BH]{BH} W.~Bruns, J.~Herzog: \emph{Cohen-Macaulay rings\@.}
Cambridge University Press, Cambridge 1993.
\bibitem[Bu]{Bu} E.~Burger: \emph{\"Uber homogene lineare
Ungleichungssysteme\@.}
Z.~angew.\ Math.\ Mech.\ \textbf{36} (1956), 135--139.
\end{thebibliography}

\bigskip\parbox{15cm}{
Universit\"at Osnabr\"uck\\
Fachbereich Mathematik/Informatik\\
D--49069 Osnabr\"uck\\
Germany\\[1ex]
\texttt{<wbruns@uos.de>}}

\end{document}

The computing times of the examples in \texttt{example} on a (fast)
\textsc{Sparc} are as follows, given in seconds:
\begin{center}
\begin{tabular}{|l||rrr|rrr|}
\hline
&\texttt{normaliz}&\texttt{-h}&\texttt{-v}&\texttt{enormalz}&\texttt{-h}&\texttt{-v}
\\\hline\hline
\texttt{rproj2}   & 0.02 &  0.03 &  0.01 &  0.2 &   0.2 &  0.2 \\
\texttt{rafa1409} & 0.03 &  0.03 &  0.02 &  0.3 &   0.2 &  0.2 \\
\texttt{rafa2310} & 0.31 &  0.31 &  0.28 &  4.4 &   4.4 &  4.0 \\
\texttt{squaref1} & 0.22 &  0.27 &  0.13 &  2.8 &   2.8 &  1.8 \\
\texttt{squaref0} & 0.79 &  0.82 &  0.14 & 12.2 &  12.2 &  1.7 \\
\texttt{rafa2416} & 4.97 & 78.26 &  2.15 & 59.7 & 144.1 & 25.8 \\
\texttt{polytop}  & 0.01 &  0.01 &  0.01 &  0.1 &   0.1 &  0.1 \\
\texttt{rees}     & 0.01 &  0.01 &  0.01 &  0.2 &   0.2 &  0.2 \\
\hline
\end{tabular}
\end{center}

% On a 133 MHz \textsc{Pentium}, \texttt{normaliz rafa2416} needs about
% 8.7 seconds.

\subsubsection{\texttt{bin/}}

This contains two executables for \textsc{Sun Sparc},
\texttt{normaliz} and \texttt{enormalz}, and two executables for
\textsc{Ms-Dos}, or \textsc{OS/2}, or \textsc{Windows} 3.x/95/NT,
\texttt{normaliz.exe} and \texttt{enormalz.exe}.
