\documentclass[11pt]{article}
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparwidth 40pt
\marginparsep 10pt
\topmargin 0pt
\headsep 10pt
\textheight 8.4in
\textwidth 6.5in
\renewcommand{\baselinestretch}{1.2}
\begin{document}
\newtheorem{lemma}{Lemma}[subsection]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{observation}[lemma]{Observation}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{example}[lemma]{Example}
\newtheorem{algorithm}[lemma]{Algorithm}
\title{\bf Computing Gr\"obner Fans of Toric Ideals}
\author{Birkett Huber \\ \\
MSRI\\
1000 Centennial Drive\\
Berkeley, CA 94720\\
{\tt birk@msri.org} \and
Rekha R. Thomas\\ \\
Dept. of Mathematics\\
Texas A \& M University\\
College Station, TX 77843\\
{\tt rekha@math.tamu.edu}}
\maketitle
\begin{abstract}
The monomial initial ideals of a graded
polynomial ideal are in bijection with the vertices of a convex
polytope known as the state polytope of the ideal. The Gr\"obner fan
of the ideal is the normal fan of its state polytope.
In this paper we present a software system called TiGERS for computing
the Gr\"obner fan of a toric ideal by enumerating the edge graph of
its state polytope. The key contributions are an inexpensive algorithm
for local change of Gr\"obner bases in toric ideals and the
identification of a reverse search tree on the vertices of the state
polytope. Using these ideas we obtain a combinatorial Gr\"obner walk
procedure for toric ideals. TiGERS has been used to compute state
polytopes with over 200,000 vertices.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Consider the polynomial ring $k[{\bf x}] := k[x_1, \ldots, x_n]$ where
$k$ is a field and an ideal $I \subset k[{\bf x}]$ that is
homogeneous with respect to a positive grading $degree(x_i) =
\omega_i \in {\bf N} \backslash \{0\}$.
We use ${\bf N}$ to denote the set of non-negative integers. The
{\em initial ideal} of $I$ with respect to a {\em term order} $\succ$
on $k[{\bf x}]$ is the {\em monomial ideal} $in_{\succ}(I) := \langle
in_{\succ}(f) \, : \, f \in I \rangle$ where $in_{\succ}(f)$ is the
{\em initial term} of $f \in I$ with respect to $\succ$. The {\em
reduced Gr\"obner basis} of $I$ with respect to $\succ$ is the unique
finite set of monic polynomials ${\cal G}_{\succ}(I) = \{g_1,
\ldots, g_t \} \subset I$ such that (i) $in_{\succ}(I) = \langle
in_{\succ}(g_1), \ldots, in_{\succ}(g_t) \rangle$ and (ii) for $i \neq j$,
no term of $g_i$ is divisible by $in_{\succ}(g_j)$. Reduced Gr\"obner
bases of polynomial ideals can be computed using {\em Buchberger's
algorithm}. See \cite{AL} or \cite{CLO} for further details.
Given an arbitrary {\em weight vector} $c \in {\bf R}^n$, and a
polynomial $f = \sum k_{\alpha}x^{\alpha} \in k[{\bf x}]$, the
{\em initial term} of $f$ with respect to $c$ is defined to be the sum of all
terms $k_{\alpha}x^{\alpha}$ in $f$ such that the inner product
$c \cdot \alpha$ is maximal. The {\em initial ideal} of $I$ with
respect to $c$ is then $in_c(I) := \langle in_c(f) \, : \, f \in I
\rangle$. If $in_c(I)$ is a monomial ideal then $c$ is said to be
{\em generic} for $I$. It is known that for a term order $\succ$ on
$k[{\bf x}]$, there exists a weight vector $c \in {\bf N}^n$ such that
$in_c(I) = in_{\succ}(I)$. In this case we say that $c$ represents $\succ$
and it can be shown that $in_c(I) = in_{\succ}(I)$ if and only if
$in_c(g) = in_{\succ}(g)$ for each $g$ in ${\cal G}_{\succ}(I)$.
Two weight vectors $c_1$ and $c_2$ in ${\bf R}^n$ are said to be
{\em equivalent modulo $I$} whenever $in_{c_1}(I) = in_{c_2}(I)$. The
set of all weight vectors that are equivalent to $c \in {\bf R}^n$ form
a relatively open polyhedral cone in ${\bf R}^n$, the closure of which
is called the {\em Gr\"obner cone} of $c$. The Gr\"obner cone of $c$
is $n$-dimensional if and only if $c$
is generic for $I$. The collection of all Gr\"obner cones
of $I$ form a {\em polyhedral fan} in ${\bf
R}^n$ called the {\em Gr\"obner fan} of $I$ \cite{MR}. Since $I$ is
homogeneous with respect to a positive grading,
this fan is, in fact, {\em complete} (i.e., covers ${\bf R}^n$) and
further, each Gr\"obner cone of $I$ contains a strictly positive vector
of ${\bf R}^n$.
The Gr\"obner fan of $I$ is the {\em normal fan} of a polytope in
${\bf R}^n$ called the {\em state polytope} of $I$ \cite{BM}, denoted
as $St(I)$. Therefore, $I$ has only
finitely many distinct reduced Gr\"obner bases as $c$ varies over
all weight vectors in ${\bf R}^n$. (See \cite{Mac} for a new proof.)
The faces of $St(I)$ are
in bijection with the distinct initial ideals of $I$, with the
vertices of $St(I)$ corresponding bijectively to the distinct monomial
initial ideals of $I$. The distinct monomial initial ideals of $I$, in turn,
are in bijection with the distinct reduced Gr\"obner bases of $I$
obtained from term orders. Hence,
computing all such initial ideals amounts to searching the {\em edge graph}
of $St(I)$. Two monomial initial ideals $in_{c_1}(I)$ and
$in_{c_2}(I)$ are said to be {\em adjacent} if
the corresponding vertices of $St(I)$ are adjacent or equivalently, if
the Gr\"obner cones of the generic weight vectors $c_1$ and $c_2$ share a
common {\em facet}. See
Chapters 1-3 in \cite{Stu} for proofs of the results quoted above
and a full discussion of Gr\"obner fans and state polytopes of graded
polynomial ideals. Algorithms for their construction are also included.
Given a matrix $A = [a_1, \ldots, a_n] \in {\bf Z}^{d \times n}$ of
rank $d$, the {\em toric ideal} of $A$, denoted as $I_A$, is the
kernel of the homomorphism $k[x_1,\ldots,x_n]
\rightarrow k[t_1^{\pm 1}, \ldots, t_d^{\pm 1}]$, such that $x_j
\mapsto t^{a_j}$ (see Chapter 4 in \cite{Stu}). The ideal $I_A$ is a
$d$-dimensional prime ideal that is
generated by the {\em binomials} $x^{u^+} - x^{u^-}$ where $u = u^+ -
u^-$ lies in the $(n-d)$-dimensional saturated lattice $ker_{\bf Z}(A):=
\{ u \in {\bf Z}^n : Au = 0 \}$. Here $u^- = (-u)^+$ and $u^+$ is
defined as $u^+_i = u_i$ if $u_i > 0$ and $u^+_i = 0$ otherwise. Hence
$u^+, u^- \in {\bf N}^n$. The mechanics of the Buchberger algorithm ensure
that every reduced Gr\"obner basis of $I_A$ again consists of finitely
many binomials of the above type. We will assume that $ker_{\bf Z}(A)
\cap {\bf N}^n = \{0\}$ which guarantees a positive integral vector
$\omega$ in the row space of $A$. Then $I_A$ is homogeneous
with respect to the grading $degree(x_i) = \omega_i$.
Let ${\cal G}_c = \{x^{\alpha_i} -
x^{\beta_i} \, : \, i = 1, \ldots, t \}$ be the reduced Gr\"obner
basis of $I_A$ with respect to a generic weight vector $c \in {\bf
R}^n$. (The positive term of a binomial in ${\cal G}_c$ is always
assumed to be the initial term with respect to $c$.) The Gr\"obner
cone of $c$ is then the $n$-dimensional polyhedral cone
$ {\cal K}_c := \{ u \in {\bf R}^n : \alpha_i \cdot u \geq \beta_i
\cdot u, \, i = 1, \ldots, t \}$
whose lineality space (${\cal K}_c \cap -{\cal K}_c$)
is the row space of $A$. We may assume that $c$ is a strictly positive
integral vector since
${\cal K}_c$ is a rational cone and $\omega \in {\cal K}_c$. Further,
$c'$ is equivalent to $c$ if and only if
$in_{c'}(x^{\alpha_i} - x^{\beta_i}) = x^{\alpha_i}$ for each binomial
$x^{\alpha_i} - x^{\beta_i} \in {\cal G}_c$. State polytopes and
Gr\"obner fans of toric ideals were studied in \cite{ST}. This paper
gives several custom-tailored construction methods for these entities
when the ideal is toric.
The Gr\"obner fan of $I_A$ has various applications: In \cite{ST} it
was used as a model for {\em sensitivity analysis} for the family
of {\em integer programs} $min \{ c \cdot x \, :\, Ax = b, \, x \in
{\bf N}^n \}$ as $b$ varies in ${\bf Z}^d$ and $c$ in ${\bf R}^n$.
The {\em secondary fan} of $A$ \cite{BFS}, \cite{GKZ} is a coarsening
of the Gr\"obner fan of $I_A$ (see Chapter 8 in \cite{Stu}). This fan has
important applications to problems in discrete geometry. In between
the secondary fan and the Gr\"obner fan of $A$ lives the {\em
hypergeometric fan} of $A$ which has been used for studying
$A$-{\em hypergeometric} differential equations using
{\em Gr\"obner deformations}
\cite{SST}. Both these coarser fans can be obtained from the Gr\"obner
fan of $I_A$. Finally, the {\em Gr\"obner walk} procedure introduced in
\cite{CKM} uses the Gr\"obner fan for Gr\"obner basis conversions.
\begin{example}\label{EX1}
Let $A := \left( \begin{array}{ccccc}
1 & 1 & 1 & 1 & 1 \\
0 & 1 & 2 & 1 & 0 \\
0 & 0 & 1 & 2 & 1
\end{array} \right )$. For ease of exposition we associate the
variables $a,b,c,d,e$ to the five columns of $A$ and consider the
toric ideal $I_A \subset k[a,b,c,d,e]$. This ideal
yields eight distinct monomial initial ideals. The state polytope
$St(I_A)$ is an
octagon in ${\bf R}^5$ and the Gr\"obner fan of $I_A$ can be drawn in
${\bf R}^2$ after moding out the row space of $A$ from each Gr\"obner
cone. Figure \ref{FIG1} shows a schematic representation of the resulting {\em
pointed} Gr\"obner fan of $I_A$. Each maximal cone is labeled by the
reduced Gr\"obner basis induced by the weight vectors in the
interior of that cone. The binomials in
a reduced Gr\"obner basis that contribute the facet inequalities of
its Gr\"obner cone are marked with dots. Notice that for two adjacent
reduced Gr\"obner bases, their common facet binomial $x^{\alpha} -
x^{\beta}$ appears in both reduced Gr\"obner bases with
$x^{\alpha}$ as initial term in one basis and $x^{\beta}$ as
initial term in the other.
\end{example}
\begin{figure}[h]
\fbox{
\setlength{\unitlength}{1.7cm}
\begin{picture}(9,6)
\put(0,2.1){
\makebox(1.8,1.2){ %G1
$\begin{array}{ll}
\bullet & a^2c-b^2e\\
& a^2d-be^2\\
\bullet & bd-ce
\end{array}$ }}
\put(0.2,4.3){
\makebox(1.8,1.2){ %G2
$\begin{array}{ll}
\bullet& b^2e-a^2c\\
\bullet& a^2d-be^2\\
&bd-ce\\
\end{array}$ }}
\put(3.4,4.5){%G4
\makebox(1.8,1.5){
$\begin{array}{ll}
\bullet & a^2d^2-ce^3\\
& b^2e-a^2c\\
\bullet & be^2-a^2d\\
& bd-ce
\end{array}$ }}
\put(6.4,4.4){ %G6
\makebox(1.8,1.6){
$\begin{array}{ll}
\bullet & ce^3-a^2d^2\\
& b^2e-a^2c\\
& be^2-a^2d\\
\bullet & bd-ce
\end{array}$ }}
\put(7.2,2.2){ %G8
\makebox(1.8,1.5){
$\begin{array}{ll}
\bullet & b^3d-a^2c^2 \\
& b^2e-a^2c\\
& be^2-a^2d\\
\bullet & ce-bd
\end{array}$ }}
\put(6.4,0.4){ %G7
\makebox(1.8,1.4){ %G4
$\begin{array}{ll}
\bullet & a^2c^2-b^3d\\
\bullet & b^2e-a^2c\\
& be^2-a^2d\\
& ce-bd
\end{array}$ }}
\put(3.4,0){
\makebox(1.8,1.2){ %G5
$\begin{array}{ll}
\bullet & a^2c-b^2e\\
\bullet & be^2-a^2d\\
& ce-bd
\end{array}$ }}
\put(1.0,0.6){
\makebox(0.2,0.2){ %G3
$\begin{array}{ll}
& a^2c-b^2e\\
\bullet & a^2d-be^2\\
\bullet & ce-bd\\
\end{array}$ }}
\put(4.5,3){\line( 1,2 ){1.5}}
\put(4.5,3){\line( 1,-2){1.5}}
\put(4.5,3){\line( -3,4 ){2.25}}
\put(4.5,3){\line( -2,-3){2}}
\put(4.5,3){\line( -4,1 ){4.5}}
\put(4.5,3){\line( -3,-1){4.5}}
\put(4.5,3){\line( 4,1 ){4.5}}
\put(4.5,3){\line( 3,-1){4.5}}
\end{picture}
}
\caption{\label{FIG1}A schematic of the Gr\"obner fan in Example \ref{EX1}}
\end{figure}
In this paper we introduce a software system called TiGERS for computing the
Gr\"obner fan of a toric ideal.
The program searches the edge graph of the state polytope $St(I_A)$ to find all
the distinct monomial initial ideals (reduced Gr\"obner bases) of $I_A$.
This search can be done in two ways: For moderate
sized examples, the graph is searched by a breadth-first search strategy
on the entire edge-graph of $St(I_A)$. This approach needs to maintain
and search the list of all Gr\"obner bases found. When $St(I_A)$ is too
large this approach will bog down and we use a {\em reverse search technique}\/
instead. This involves a depth-first search
on a subgraph of the edge graph of $St(I_A)$ called the reverse search tree,
and can be implemented so that no more than one Gr\"obner basis ever
needs to be stored.
In Section 2 we give an overview of the main algorithm in
TiGERS and describe the reverse search procedure.
These ideas allow {\em
combinatorial Gr\"obner walks} in toric ideals.
For each reduced Gr\"obner basis found,
the algorithm does two main local computations. The first is to
determine all the facets of that Gr\"obner cone and the
second is to determine an adjacent Gr\"obner basis to the
current one. In Section 3 we give an algorithm for
local change of Gr\"obner bases in toric ideals based on
\cite{CKM}. Unlike usual local change
algorithms, our procedure does not require any weight vectors to be
computed. We then discuss some special tricks
to find the facets of a fixed Gr\"obner cone in the case of toric
ideals. Section 4 reports computational experience with TiGERS.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The main algorithm in TiGERS}
Let ${\cal G}_c = \{ x^{\alpha_i} - x^{\beta_i}, \, i = 1,
\ldots, t \}$ be the reduced Gr\"obner basis of $I_A$ with respect to
the generic weight vector $c \in {\bf R}^n$.
An inequality $\alpha_k \cdot u \geq
\beta_k \cdot u$, $k \in \{1,\ldots,t\}$ is irredundant for the
Gr\"obner cone ${\cal K}_c = \{ u \in {\bf R}^n \, : \, \alpha_i \cdot
u \geq \beta_i \cdot u, \, i = 1, \ldots, t \}$ if the relaxed cone
$\{ u \in {\bf R}^n \, : \, \alpha_i \cdot u \geq \beta_i \cdot u, \,
i = 1, \ldots, t, i \neq k \}$ properly contains ${\cal K}_c$. If
$\alpha_k \cdot u \geq \beta_k \cdot u$ is irredundant for ${\cal
K}_c$ then ${\cal K}_c \cap \{u \in {\bf R}^n \, : \, \alpha_k \cdot u
= \beta_k \cdot u \}$ is called a {\em facet} of ${\cal K}_c$ and
$x^{\alpha_k} - x^{\beta_k}$ is a {\em facet binomial} of ${\cal G}_c$.
\begin{lemma}\cite{ST} \label{facets}
The binomial $x^{\alpha_k} - x^{\beta_k} \in {\cal
G}_c$ is a facet binomial of ${\cal G}_c$ if and only if
the linear system $\{u \in {\bf R}^n : \alpha_i \cdot u \geq \beta_i
\cdot u \,, \, i = 1,\ldots,t,\, i \neq k \} \cup
\{ u \in {\bf R}^n : \beta_k \cdot u \geq \alpha_k \cdot u \}$ is feasible.
\end{lemma}
Therefore, all facets of the Gr\"obner cone ${\cal K}_c$ can be found
by checking the feasibility of $t$ systems of linear inequalities,
which in turn can be done by linear programming.
In practice this can be computationally expensive when $t$ is large
and we discuss certain speed ups in Section 3.2.
Suppose $x^{\alpha} - x^{\beta}$ is a
facet binomial of ${\cal G}_c$
such that $in_c(x^{\alpha} - x^{\beta}) = x^{\alpha}$ and ${\cal G}_{c'}$
be adjacent to ${\cal G}_c$ with $in_{c'}(x^{\alpha} - x^{\beta})
= x^{\beta}$. In order to compute the edge graph of $St(I_A)$,
we require a subroutine to make a local change of reduced
Gr\"obner bases from ${\cal G}_c$ to ${\cal G}_{c'}$ through the facet
given by $x^{\alpha} - x^{\beta}$. We use ${flip({\cal G}_c, x^{\alpha} -
x^{\beta})}$ to denote both the subroutine that yields ${\cal G}_{c'}$
from ${\cal G}_c$ as well as the reduced Gr\"obner basis
${\cal G}_{c'}$ that results from the ``flip''. In Section 3.1 we
describe the precise local change algorithm in TiGERS.
\begin{remark}{\em
If $x^{\alpha} - x^{\beta}$ lies in the reduced Gr\"obner basis of a
toric ideal, then the supports of $\alpha$ and $\beta$ are disjoint.
This guarantees that each facet in a toric Gr\"obner cone corresponds
to precisely one binomial in the corresponding Gr\"obner basis.
However, this is not true for general homogeneous
binomial ideals. Consider $J = \langle
b^3d-b^2ce, a2c-b2e, bcd-c2e \rangle$. Under the reverse lexicographic
order $a \succ c \succ d \succ e \succ b$, its reduced Gr\"obner basis is
$G = \{ ceb^2-db^3, c^2e-cdb, a^2db^3-e^2b^4, a^2c-eb^2 \}$. The
inequality $u_3 + u_5 \geq u_2 + u_4$ is a facet inequality of the
Gr\"obner cone of $G$. For $\omega$ in the relative interior of this facet,
we get both $in_{\omega}(ceb^2-db^3) = ceb^2-db^3$ and
$in_{\omega}(c^2e-cdb) = c^2e-cdb$.}
\end{remark}
\begin{algorithm}
Enumerating the edge graph of $St(I_A)$ via breadth-first search.
\begin{tabbing}
xx\=xx\=xx\=xx\=\kill
{\bf Input:} Any reduced Gr\"obner basis ${\cal G}_0$ of $I_A$.\\
{\bf Output:} All reduced Gr\"obner bases of $I_A$ (all vertices of
$St(I_A)$).\\
\>{\tt Todo} := $\left[{\cal G}_0\right]$; \\
\>{\tt Verts} := $\left[ \,\, \right]$;\\
\> While(${\tt Todo}$ not empty) do\\
\> \> ${\cal G}$ := first-element-in({\tt Todo});\\
\> \> Remove ${\cal G}$ from {\tt Todo};\\
\> \> add ${\cal G}$ to {\tt Verts};\\
\> \> determine list $L$ of facet binomials of ${\cal G}$\\
\> \> for each $x^{\alpha} - x^{\beta}$ in $L$ do\\
\> \> \> Compute $G'=flip({\cal G},x^{\alpha}-x^{\beta})$\\
% \>\>\> If ${\cal G}'$ not in {\tt Todo} or {\tt Verts} then
% add ${\cal G}'$ to the beginning of the list {\tt Todo};\\
\>\>\> If ${\cal G}'\not\in {\tt Todo}\cup{\tt Verts}$ then
add ${\cal G}'$ to {\tt Todo};\\
\>\>End \\
\>End\\
\> output {\tt Verts}
\end{tabbing}
\end{algorithm}
This algorithm works well in practice but does have the drawback that all
vertices must be stored, and that every time a vertex is visited it must
be checked against all other vertices seen thus far in order to
determine if it is indeed a new vertex. The storage and search
costs involved in this procedure can become prohibitive as the size of
$St(I_A)$ increases. As an example consider
$A := \left( \begin{array}{ccccccccc}
3 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\
0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 3
\end{array} \right )$. The ideal $I_A$ involves only nine variables
and most reduced Gr\"obner bases of this ideal have fewer than
$36$ elements each of degree no greater than seven. Yet, $St(I_A)$ has
$54,828$ vertices and our breadth first search algorithm was exhausting
a personal computer with 64 kilobytes of memory before getting through about
$13,000$ vertices. In order to push this calculation through we
resorted to the reverse enumeration paradigm of Avis and Fukuda
\cite{AF}. The basic idea there is to do a depth first search on a directed
subgraph of $St(I_A)$.
We say that a polynomial $f \in k[{\bf x}]$ is {\em marked} by a
term order $\succ$ on $k[{\bf x}]$, if the initial term of $f$
with respect to $\succ$ has been distinguished from among all terms in
$f$. A polynomial $f$ that has been marked with respect to $\succ$ is
said to be {\em mismarked} with respect to $\succ'$,
if $in_{\succ}(f) \neq in_{\succ'}(f)$.
\begin{lemma} \label{marking}
Let ${\cal G}_{\succ}$ be the reduced Gr\"obner basis of $I_A$ with respect
to the term order $\succ$. Then for a term order $\succ' \neq
\succ$, the reduced Gr\"obner basis ${\cal G}_{\succ'}$ equals ${\cal
G}_{\succ}$ if and only if no facet
binomial of ${\cal G}_{\succ}$ is mismarked with respect to $\succ'$.
\end{lemma}
\noindent{\em Proof:} Suppose no facet binomial of ${\cal G}_{\succ}$
is mismarked with respect to $\succ'$ and let $c'$ be a weight vector
from the interior of the Gr\"obner cone ${\cal K}_{\succ'}$. Then for
each facet binomial $x^{\alpha} - x^{\beta}$ in ${\cal G}_{\succ}$, we
have $c' \cdot \alpha > c' \cdot \beta$
which implies that $c'$ lies in the interior of the Gr\"obner cone
${\cal K}_{\succ}$. Hence ${\cal K}_{\succ'} = {\cal K}_{\succ}$ which
implies that ${\cal G}_{\succ} = {\cal G}_{\succ'}$. Conversely, if
${\cal G}_{\succ} = {\cal G}_{\succ'}$, then no binomial in ${\cal
G}_{\succ}$ is mismarked with respect to $\succ'$.
\begin{definition} \label{def-tree}
For a given term order $\succ$ we define the
{\em reverse search tree $T_\succ(I_A)$} as follows:\\
The vertices of $T_{\succ}(I_A)$ are the vertices of $St(I_A)$
(i.e. the various reduced Gr\"obner bases of $I_A$ arising
from term orders). For two reduced Gr\"obner bases ${\cal G}_i$ and
${\cal G}_j$, $[{\cal G}_i,{\cal G}_j]$ directed from
${\cal G}_i$ to ${\cal G}_j$ is an edge of
$T_\succ(I_A)$ if ${\cal G}_j$ is obtained from ${\cal G}_i$ by the
subroutine $flip({\cal G}_i,x^{\alpha} - x^{\beta})$ where $x^{\alpha} -
x^{\beta}$ is the unique facet binomial of ${\cal G}_i$
whose leading term is lexicographically maximal
among all facet binomials of ${\cal G}_i$ that are mismarked with
respect to $\succ$.
\end{definition}
%The following theorem proves that $T_\succ(I_A)$ is indeed a tree.
\begin{theorem}
The reverse search tree $T_\succ(I_A)$ is an acyclic directed graph
with a unique sink.
\end{theorem}
\noindent{\em Proof:}
By Lemma~\ref{marking} each reduced Gr\"obner basis ${\cal G}$ of
$I_A$ (vertex of $St(I_A)$) except ${\cal G}_\succ$ has at least one
mismarked facet binomial with respect to $\succ$. By the definition of
$T_\succ(I_A)$, each such ${\cal G}$ has a unique adjacent
reduced Gr\"obner basis given by $flip({\cal G},x^{\alpha} -
x^{\beta})$ where $x^{\alpha} - x^{\beta}$ is the unique facet
binomial of ${\cal G}$ whose leading term is lexicographically maximal
among all mismarked facet binomials of ${\cal G}$. Therefore
$T_\succ(I_A)$ is a directed graph such that the
out-degree of ${\cal G}_{\succ}$ in $T_\succ(I_A)$ is zero and of all
other reduced Gr\"obner bases is one.
Suppose there was a cycle $C = (v_1, \ldots, v_l)$ of length $l$ in
$T_\succ(I_A)$ where vertex $v_i$ corresponds to the reduced
Gr\"obner basis ${\cal G}_i$ of $I_A$ and $v_{l+1} = v_1$ and
${\cal G}_{l+1} = {\cal G}_1$. If $x^{\alpha_i}-x^{\beta_i}$ is
the common facet binomial of ${\cal G}_i$ and ${\cal G}_{i+1}$ with
$x^{\alpha_i}$ the leading term with respect to ${\cal G}_i$ and
$x^{\beta_i}$ the leading term with respect to ${\cal G}_{i+1}$
for $i=1,\ldots,l$, then $v_{i+1} - v_i =
\beta_i - \alpha_i$ for $i=1,\ldots, l$. Since $C$ is a cycle in
$T_\succ(I_A)$ we get $(\beta_1 - \alpha_1) + (\beta_2 -
\alpha_2) + \cdots + (\beta_l - \alpha_l) = 0$. However, each binomial
$x^{\alpha_i}-x^{\beta_i}$ for $i=1,\ldots,l$ is mismarked with
respect to $\succ$ which implies that for a weight vector $c$
representing $\succ$ we have, $c \cdot (\beta_i - \alpha_i) > 0$.
This leads to the contradiction
$0 = c \cdot
\sum_{i=1}^{l} ({\beta_i}-{\alpha_i}) = \sum_{i=1}^{l}
c \cdot (\beta_i - \alpha_i) > 0 $.
\begin{corollary}\label{unique-path}
From any reduced Gr\"obner basis ${\cal G}_c$ of $I_A$ there is a
unique path in the reverse search tree $T_\succ(I_A)$ to the sink
${\cal G}_\succ$.
\end{corollary}
Corollary~\ref{unique-path} proves that toric ideals admit
combinatorial Gr\"obner walks that can be used for converting one
reduced Gr\"obner basis of $I_A$ into another. Given any reduced
Gr\"obner basis ${\cal G}$ of $I_A$ and any term order $\succ$, we can
move from ${\cal G}$ to ${\cal G}_\succ$ by tracing the unique path in the
reverse search tree $T_\succ(I_A)$ from ${\cal G}$ to ${\cal G}_\succ$.
Unlike in the usual Gr\"obner walk procedure \cite{CKM},\cite{AGK}
to convert one Gr\"obner basis into another there are no explicit cost
vectors involved in these walks. These combinatorial walks also have
the advantage that there is never the danger of walking through a
lower dimensional face of a Gr\"obner cone thus eliminating several
numerical considerations that otherwise have to be dealt with. The
trade off is that at every vertex of the state polytope, all facets of
the current Gr\"obner cone have to be computed which can be highly
non-trivial for general ideals, but is relatively easy for toric ideals.
\begin{algorithm}
Enumerating the edge graph of $St(I_A)$ via reverse search.
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=\kill
{\bf Input:} A reduced Gr\"obner basis ${\cal R}_\succ$ of $I_A$ and its
term order $\succ$.\\
{\bf Output:} All reduced Gr\"obner bases of $I_A$ (all vertices of
$St(I_A)$).\\
\> set ${\cal G} := {\cal R}_\succ$; j:=0 ; L := list of facet binomials of ${\cal G}$ which are marked by $\succ$\\
\> output ${\cal G}$\\
\> repeat \\
\> \> while $j < |L|$ do \\
\> \> \> $j := j + 1$.\\
\> \> \> ${\cal G}':=flip({\cal G},L[j])$;\\
\> \> \> if [${\cal G}'$,${\cal G}$] in $T_{\succ}(I_A)$ then\\
\> \> \> \> ${\cal G}$:= {\cal G}'; $j := 0$; L := list of facets of
${\cal G}$ marked by $\succ$ \\
\> \> \> \> output ${\cal G}$\\
\> \> \> endif\\
\> \> endwhile\\
\> \> If ${\cal G} \neq {\cal R}_{\succ}$ then\\
\> \> \> ${\cal G}'$ := unique element such that [${\cal G}$,${\cal G}'$]
in $T_{\succ}(I_A)$;
$j:=0$; L := list of facets of ${\cal G}'$ marked by $\succ$\\
\> \> \>repeat $j:=j+1$ until the common facet of ${\cal G}$ and ${\cal G'}$
is the $j$th facet of $L$.\\
\> \> \> ${\cal G}$ := ${\cal G}'$\\
\> \> endif\\
\> until ${\cal G} = {\cal R}_{\succ}$ and $j = |L|$.
\end{tabbing}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Local Computations}
Having given an overview of the algorithm in TiGERS for computing the
Gr\"obner fan of a toric ideal, we now focus on the computations
that have to be made at a fixed reduced Gr\"obner basis encountered
while searching the edge graph of $St(I_A)$. The two main issues here
are (i) how to compute a Gr\"obner basis that shares a prescribed
facet binomial with the current basis and (ii) how to compute all the
facets of a toric Gr\"obner cone.
\subsection{Local change of Gr\"obner bases in toric ideals}
\begin{algorithm} Local change of reduced Gr\"obner bases in $I_A$.\\
(a specialization of \cite{CKM} and Subroutine 3.7 in \cite{Stu}).
\label{localchange}
\end{algorithm}
\noindent{\bf Input:} (i) A reduced Gr\"obner basis ${\cal G} =\{
{\underline x^{a_k}}-x^{b_k} : k = 1,..,t \}$ of $I_A$.\\
(The weight vector inducing ${\cal G}$ is generic and the underlined terms
are the leading terms.)\\
(ii) A prescribed facet binomial ${\underline x^{a_i}} - x^{b_i}$ of ${\cal G}$.\\
\noindent{\bf Output:} The reduced Gr\"obner basis adjacent to ${\cal
G}$ in which ${\underline x^{b_i}} - x^{a_i}$ is a facet binomial.
\vskip .2cm
\indent \indent \indent a. Let $Old :=
\{{\underline x^{a_i}}-x^{b_i}\} \cup \{{\underline x^{a_j}} \, : \,
{\underline x^{a_j}}-x^{b_j} \in {\cal G},\, j \neq i \}$.\\
\indent \indent \indent b. Let $Temp$ be got from
$Old$ by switching the marking on {\bf the} binomial in $Old$.\\
\indent \indent \indent \indent i.e.,
$Temp := \{ {\underline x^{b_i}}-x^{a_i} \} \cup
\{{\underline x^{a_j}} \, : \, x^{a_j} \in Old \}$. \\
\indent \indent \indent c. Compute the reduced Gr\"obner basis
of $Temp$ with respect to the new marking.
\indent \indent \indent \indent Store the (marked)
result in $New$.\\
\indent \indent \indent d. Set ${\cal G}' := \emptyset$\\
\indent \indent \indent e. For each $h$ in $New$ DO\\
\indent \indent \indent \indent (i) Reduce $h$ to zero modulo
$Old$ keeping track of the coefficients during reduction.
\indent \indent \indent \indent \indent This gives the representation
\[ h = \sum_{g \in Old} p_g \cdot g \]
\indent \indent \indent \indent (ii) Compute the polynomial
\[ \sum_{full(g) \in {\cal G}} p_g \cdot full(g) \]
\indent \indent \indent \indent \indent and add it to the set ${\cal G}'$.
($full(g) \in {\cal G}$ is the completion of $g \in Old$.)\\
\indent \indent \indent f. Auto-reduce ${\cal G}'$ with respect
to the markings in $New$ to get ${\cal G}_{new}$. \\
Then ${\cal G}_{new}$ is the reduced Gr\"obner
basis adjacent to ${\cal G}$ such that ${\underline x^{a_i}} -
x^{b_i}$ is a facet binomial in ${\cal G}$ and ${\underline x^{b_i}} -
x^{a_i}$ is a facet binomial in ${\cal G}_{new}$.\\
\noindent {\sl Proof of correctness:} Let ${\cal K}$ and ${\cal
K}_{new}$ be the Gr\"obner cones of ${\cal G}$ and ${\cal G}_{new}$
respectively. The linear span of the common facet of
${\cal K}$ and ${\cal K}_{new}$ is $\{u \in {\bf R}^n : a_i \cdot u
= b_i \cdot u \}$. Let $c_1 \in interior({\cal K})$,
$c_2 \in interior({\cal K}_{new})$ and $c$ be a vector in the relative
interior of $K \cap K_{new}$. By definition, $Old = in_c({\cal G}) :=
\{ in_c(f) : f \in {\cal G} \}$
and with respect to the markings specified in Step a, $Old$ is the
reduced Gr\"obner basis of $in_c(I_A)$ with respect to $c_1$. Since
$Temp$ is got from $Old$ by simply reversing the marking on the facet
binomial $x^{a_i} - x^{b_i}$, $Temp$ is a generating set for $in_c(I_A)$.
We first show that the set $New$ computed in Step c, using $Temp$ as
input, is the reduced Gr\"obner basis of $in_c(I_A)$ with respect to
$c_2$. Clearly the marked monomials in $Temp$ are
their own initial terms with respect to $c_2$. The non-trivial $S$-pair
computations in Step c are those between a monomial $x^{a_j}$,\, $j
\neq i$, and the
binomial ${\underline x^{b_i}}-x^{a_i}$. This results in a monomial
which either reduces to zero with respect to the current partial
Gr\"obner basis or reduces to a monomial that gets added to the
current partial Gr\"obner basis. There is no point during this process
at which an unmarked binomial is produced that is required to be marked.
No binomials are produced during such an $S$-pair
reduction either. Hence all subsequent $S$-pair computations are
also of the above nature and so in fact, the set $New$ is as
claimed above and consists of the binomial ${\underline
x^{b_i}}-x^{a_i}$ along with monomials some of which were possibly
produced during the Buchberger process. Steps d and e simply lift
$New$ to a minimal Gr\"obner basis ${\cal G'}$ of $I_A$ with respect
to $c_2$. Finally, Step f auto-reduces this minimal Gr\"obner basis
to the reduced Gr\"obner basis ${\cal G}_{new}$ of $I_A$ with
respect to $c_2$. \\
The most important computational advantage of the above local change
algorithm is that it does not require the computation of a weight
vector in the interior of ${\cal K}_{new}$ in order to compute the
reduced Gr\"obner basis ${\cal G}_{new}$. This is possible due to the
binomial/monomial nature of all intermediate sets produced during the
algorithm. The weight vectors are carried implicitly in the markings
of these elements. This observation leads to considerable speed up of
the procedure.
\begin{remark} \label{dianeobservation}
As in the proof of Algorithm~\ref{localchange}, let
$c_1 \in interior({\cal K})$ and $c_2 \in interior({\cal K}_{new})$.
Then notice that $in_{c_1}(I_A)$ is the initial ideal
of $W_{a_i - b_i} := \langle x^{a_i} - x^{b_i} \rangle + \langle
x^{a_j} \, : \, i \neq j, \, x^{a_j} \in in_{c_1}(I_A) \rangle$ with
respect to the marking $x^{a_i} > x^{b_i}$ while $in_{c_2}(I_A)$ is
the initial ideal of $W_{a_i - b_i}$ with respect to $x^{b_i} >
x^{a_i}$. See \cite{MT} for a generalization of this observation to
the theory of {\em $A$-graded ideals} (see Chapter 10 in \cite{Stu})
and the {\em toric Hilbert scheme}.
\end{remark}
\begin{example}{\em For
$A := \left( \begin{array}{cccccc} 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 2 & 1 & 0 \\
0 & 0 & 1 & 2 & 1 \end{array}
\right )$, consider the adjacent reduced Gr\"obner bases ${\cal G}_1$
and ${\cal G}_2$ that share the facet binomial $a^2d-be^2$.
The basis ${\cal G}_1 = \{ bd-ce, a^2d-be^2, b^2e-a^2c \}$ has facet
binomials $a^2d-be^2$ and $b^2e-a^2c$ and ${\cal G}_2 =
\{bd-ce, be^2-a^2d, a^2d^2-ce^3, b^2e-a^2c \}$ has facet binomials
$a^2d^2-ce^3$ and $be^2-a^2d$. We use Algorithm~\ref{localchange} to
compute ${\cal G}_2$ from ${\cal G}_1$.\\
\noindent{\bf Step a.} $Old := \{ a^2d-be^2, bd, b^2e \}$.\\
\noindent{\bf Step b.} $Temp := \{ be^2-a^2d, bd, b^2e \}$.\\
\noindent{\bf Step c.} (i) $S$-pair$(be^2-a^2d,bd) = a^2d^2$.\\
$ Temp = \{ be^2-a^2d, bd, b^2e, a^2d^2 \}$.\\
(ii) $S$-pair$(be^2-a^2d, b^2e) = a^2bd \rightarrow 0$.\\
(iii) $S$-pair$(be^2-a^2d,a^2d^2) \rightarrow 0$.\\
Therefore $New = \{ be^2-a^2d, bd, b^2e, a^2d^2 \}$.\\
\noindent{\bf Step d.} ${\cal G}' := \emptyset$.\\
\noindent{\bf Step e.}
$be^2-a^2d = -1(a^2d-be^2)$. Therefore it lifts to $-1(full(a^2d-be^2))
= -1(a^2d-be^2) = be^2-a^2d$.\\
$bd = 1(bd)$. Therefore it lifts to $full(bd) = bd-ce$.\\
$b^2e = 1(b^2e)$. Therefore it lifts to $full(b^2e) = b^2e-a^2c$.\\
$a^2d^2 = d(a^2d-be^2) + e^2(bd)$.
Therefore it lifts to $d(full(a^2d-be^2)) + e^2(full(bd)) =
d(a^2d-be^2)+e^2(bd-ce) = a^2d^2 - bde^2 + bde^2 - ce^3 = a^2d^2 - ce^3$.\\
Hence ${\cal G}' = \{ be^2-a^2d, bd-ce, b^2e-a^2c, a^2d^2-ce^3\}$.\\
\noindent{\bf Step f.} ${\cal G}_{new} =
\{ be^2-a^2d, bd-ce, b^2e-a^2c, a^2d^2-ce^3\}$.}
\end{example}
\subsection{Finding the facets of a toric Gr\"obner cone}
For a general ideal, the Gr\"obner cone of one of its reduced
Gr\"obner bases is described by a large set of inequalities many of
which are redundant. Even for a toric ideal, empirical evidence
shows that the number of facet binomials of a reduced Gr\"obner basis may
be much smaller than the cardinality of the Gr\"obner basis. In fact,
it was conjectured in \cite{ST} that there is a function $\phi : {\bf
N} \rightarrow {\bf N}$ such that the number of facet binomials of a
reduced Gr\"obner basis of $I_A$ of codimension $k$ is bounded above
by $\phi(k)$. As a special case, it was conjectured in \cite{ST} that
$\phi(3) = 4$ based on empirical evidence with existing codes at the
time. Recently, Serkan Hosten and Diane Maclagan have found
counterexamples to this second conjecture using TiGERS. Lower bounds for
$\phi$ are given in \cite{ST}, although no good upper bound is known
for the number of facets of a toric Gr\"obner cone. Hence,
identifying the facet binomials in a reduced Gr\"obner basis can
become a computationally expensive subroutine during the computation
of the Gr\"obner fan. In this section we discuss several ways to find
the facet binomials of a Gr\"obner cone in the case of a toric ideal.
A first algorithm to compute the facets of a toric Gr\"obner cone
follows from Lemma~\ref{facets}. In practice this
can be an expensive procedure since we need to solve as many linear
programs as the cardinality of ${\cal G}$ and most binomials in ${\cal
G}$ are not facet binomials.
\begin{algorithm} How to find the facet binomials of a reduced
Gr\"obner basis of $I_A$. \label{second}
\end{algorithm}
\noindent{\bf Input:} A reduced Gr\"obner basis ${\cal G} =
\{ {\underline x^{a_i}}-x^{b_i} : i = 1,..,t \}$ of $I_A$.\\
\noindent{\bf Output:} The facet binomials of ${\cal G}$.\\
\indent Set Facets := $\emptyset$.\\
\indent For each binomial ${\underline x^{a_i}}-x^{b_i}$ in ${\cal G}$
do \\
\indent \indent If $a_i - b_i$ is not in the cone generated
by the vectors $\{a_j - b_j : {\underline x^{a_j}}-x^{b_j} \in {\cal
G}, i \neq j \}$\\
\indent \indent then Facets := Facets $\cup$ $\{x^{a_i}-x^{b_i}\}$.\\
\indent Output Facets.\\
Algorithm~\ref{second} is dual to the algorithm suggested by
Lemma~\ref{facets} since $a_i \cdot u \geq b_i
\cdot u$ is a facet inequality of the Gr\"obner cone ${\cal K}$
of ${\cal G}$ if and only if $a_i - b_i$ is an extreme
ray (essential generator) of ${\cal K}^{\ast} := \{ v \in {\bf R}^n :
v \cdot u \geq 0, \, \forall u \in {\cal K}\}$ the polar cone of
${\cal K}$. The vector $a_i - b_i$ is an extreme ray of ${\cal
K}^{\ast}$ if and only if
$a_i - b_i$ cannot be expressed as a non-negative linear combination
of the vectors $a_j - b_j$, $i \neq j$ where ${\underline
x^{a_j}}-x^{b_j} \in {\cal G}$. Algorithm~\ref{second} can be
implemented either by solving one linear program per binomial in
${\cal G}$ or finding a generator representation of the cone ${\cal
K}^{\ast}$ using a convex hull package. We also obtain an easy
sufficient condition for a binomial in ${\cal G}$ to be a facet binomial.
\begin{lemma}
Let ${\underline x^{a_i}}-x^{b_i}$ be an element of a reduced
Gr\"obner basis ${\cal G}$ of $I_A \subset k[x_1, \ldots, x_n]$ and
$x_k$ be a variable in $k[x_1, \ldots, x_n]$ such that $x_k$ divides
the leading term $x^{a_i}$ (respectively, the trailing term $x^{b_i}$)
of ${\underline x^{a_i}}-x^{b_i}$ but does not divide the leading terms
(respectively, trailing terms) of any other binomial in ${\cal G}$.
Then ${\underline x^{a_i}}-x^{b_i}$ is a facet binomial of ${\cal G}$.
\end{lemma}
\noindent{\sl Proof:} If $k$ is in the support of $a_i$ (respectively
$b_i$) but not in the support of $a_j$ (respectively $b_j$) for $j
\neq i$, $j = 1,\ldots,t$, then $a_i - b_i$ cannot be a non-negative
linear combination of $a_j - b_j$ for $j \neq i$, $j =
1,\ldots,t$. Hence $a_i - b_i$ is an extreme ray of the cone polar to
the Gr\"obner cone of ${\cal G}$.\\
We now describe an algorithm to find a superset of the facet binomials
of a fixed reduced Gr\"obner basis of $I_A$ that does not require
linear programming. Our idea comes from results in \cite{MT}
(c.f. Remark~\ref{dianeobservation}).
\begin{theorem} \cite{MT} \label{flippability}
Let ${\cal G}_c$ be the reduced Gr\"obner basis of
$I_A$ with respect to the generic weight vector $c \in {\bf R}^n$.
Then $x^a - x^b \in {\cal G}_c$ is a facet binomial of ${\cal G}_c$
only if $in_c(I_A)$ is the initial ideal of $W_{a-b} := \langle x^a -
x^b \rangle + \langle x^c \, : \, x^c \in in_c(I_A), \, x^c \neq x^a
\rangle$ with respect to $x^a > x^b$.
\end{theorem}
The exact result in \cite{MT} is that if $x^a-x^b \in {\cal G}_c$
and $in_c(I_A)$ is the initial ideal of $W_{a-b}$ with respect to
$x^a > x^b$, then the initial
ideal $M$ of $W_{a-b}$ with respect to $x^b > x^a$ has the same
$A$-graded Hilbert function as $in_c(I_A)$. The latter is a necessary
condition for $M$ to be an initial ideal of $I_A$. For $M$ to be an
adjacent initial ideal to $in_c(I_A)$, you need the additional
geometric requirement that $M$ and $in_c(I_A)$ share the facet given
by $x^a-x^b$. Hence the binomials in ${\cal G}_c$ that satisfy the
condition in Theorem~\ref{flippability} form a superset of the facet
binomials of ${\cal G}_c$. Once this superset has been found,
we use linear programming as before to identify the true facet binomials.
\begin{algorithm}\label{third}
How to find a superset of the facet binomials of a reduced Gr\"obner
basis of $I_A$.
\end{algorithm}
\noindent {\bf Input:} A reduced Gr\"obner basis ${\cal G}_c$ of
$I_A$.\\
\noindent{\bf Output:} A superset $SS$ of the facet binomials of
${\cal G}_c$.\\
\noindent Set $SS := \emptyset$\\
\indent For $x^a - x^b \in {\cal G}_c$ do \\
\indent \indent Let $W_{a-b} := \langle x^a - x^b \rangle + \langle
x^c \, : \, x^c \in in_c(I_A), \, x^c \neq x^a \rangle$.\\
\indent \indent If $in_c(I_A)$ is the initial ideal of $W_{a-b}$ with
respect to $x^a > x^b$ then $SS := SS$ union $\{x^a-x^b\}$.\\
Output $SS$.\\
We remark that computing the reduced Gr\"obner basis and hence the
initial ideal of $W_{a-b}$ with respect to $x^a > x^b$ proceeds
exactly as in Algorithm~\ref{localchange} and is possible because of
the specific monomial/binomial structure of $W_{a-b}$. Surprisingly
it turns out that using Algorithm~\ref{third} can often result in
a $50\%$ speed up over using linear programming alone.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Computational Experience}
The algorithms described in this paper have been implemented in {\tt C}
in a program called TiGERS which is available from the authors.
In this section we will describe some implementation issues,
optimizations and timings.
All timings in Table~\ref{TIMING} were obtained by running TiGERS on
a dual processor Pentium 450 with $1GB$ of RAM. With each example
problem, we list the following information about its state polytope:
$d$ its dimension, $f_0$ the number of vertices, $f_1$ the number of
edges, and $td$ the tree depth -- the longest chain in the reverse
search tree. We also list $mn$, the cardinality of the largest
Gr\"obner basis computed, $mf$, the largest number of facets in any
Gr\"obner basis, and $md$, the highest degree of a binomial
appearing in any of the Gr\"obner bases.
Timings are then given both for exhaustive search and reverse
search. Those in parentheses are timings using Algorithm~\ref{third}
to cut down on the number of linear programs needed to find facets.
We first give a brief description of the examples in
Table~\ref{TIMING}. The first four examples are unrelated:
In {\tt pent} the matrix $A = \left( \begin{array}{ccccc}
1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1
\end{array} \right )$ the convex hull of whose columns is a pentagon
in the plane.
The matrix for ${\tt V23}$ is $A = \left( \begin{array}{cccccc}
2 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 &
2 \end{array} \right )$ whose toric variety is the second Veronese
embedding of ${\bf P}^2$, while $PV33$ refers to the {\em pinched
Veronese}\/ surface for which $A = \left (
\begin{array}{ccccccccc} 3 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 3
\end{array} \right )$. The symbol {\tt gti} stands for the generic
toric ideal from Example 4.5 in \cite{PS} for which
$A = \left( \begin{array}{cccc} 20 & 24 & 25 & 31 \end{array} \right
)$. Examples $K5$ and $K6$ are specific instances of $Kn$, the
complete graph on $n$ vertices. The matrix associated to $Kn$ is the
node-edge incidence matrix of the graph (see Chapter 9 in \cite{Stu}).
The matrix $An := \left( 1 \,\,2\,\,3\,\,\ldots n \right )$ and the
Gr\"obner basis elements of the toric ideal $I_{An}$ correspond to
{\em primitive partition identities} with largest part $n$ (see Chapter 6 in
\cite{Stu} for details). The name $D r \times s$ refers to the $(r+s)
\times rs$ node-edge incidence matrix of an
undirected bipartite graph with $r$ nodes in one vertex class and $s$ nodes
in the other.
The exhaustive search approach required a large amount of memory - in
the A9 example for instance, it was using about 600M by the end. In
addition to this, the amount of time needed to determine if a vertex
has been seen increases as the number of vertices found
increases. Even when memory size is not an issue we found that the
reverse search approach could end up by being faster than
the exhaustive search (see the A9 example).
On the other hand, the reverse search implementation requires
us to traverse every edge and then check if it belonged to the reverse
search tree by finding the down edge for the new vertex.
If the edge used belongs to the reverse search tree, we keep the new vertex,
otherwise we discard it knowing that it has been seen before or will
be seen again. Thus instead of a large list search
we need only find the first mismarked facet binomial to decide whether
a vertex should be output. Furthermore, at each node we keep, we must
recompute its facet list every time we pass through it. By comparison
the exhaustive search algorithm required us to find facets only once per
vertex. One trick that we used to mitigate this
re-computation of facets was to save vertices and facet information
every time we went up in the tree,
so as to avoid recomputing the facets already visited. While this
approach means that we are no longer storing just one Gr\"obner basis, the
amount of storage required is still quite small, being bounded by the
tree depth. In all the examples listed, the reverse search
(with caching) ran in under 750K.
We conclude by drawing attention to the last entry in
Table~\ref{TIMING} denoted as {\tt HM} for which $A =
(247\,\,248\,\,345\,\,15)$. This was the original counter example found by
Hosten and Maclagan (c.f. page 10), using TiGERS, to the conjecture
that the maximum valency of a vertex in the state polytope of a corank
three matrix is four \cite{ST}.
\begin{table}[hbt]
\begin{tabular}{||c||l|l|l|l||l|l|l||l|l||}\hline
Name & d & $f_0$ & $f_1$ &td & mn & mf & md & RS & ES \\
\hline\hline
pent& 2& 8& 8& 4& 4& 2& 4& 0.00 & 0.00\\
V23 & 3& 29& 45& 6& 7& 4& 3& 0.02 & 0.02(0.01) \\
gti & 3& 288& 467&30& 18& 4& 31& 2.30(1.27)& 1.50(0.76) \\
PV33& 6& 54828& 190253&48& 36& 12& 7& (4343.31)& (3731.24) \\
\hline
K5 & 5 & 102 & 255 &14 & 11 & 5 & 3 & 0.36(0.32) & 0.28(0.24) \\
K6 & 9 & 195720 & &56 & 37 & 14 & 4 & 110111.68(50662.29)& \\
% K7 & 14 & &- &- & - & - & - & - & -\\
\hline
%---------------------------------------------------------
%-- Familly related to primitive partition identities --
%-- AN=[1,2,...,N] ---------------------------------------
%---------------------------------------------------------
A4& 3 & 20& 31& 6& 8& 4& 4& 0.01( 0.01)&0.01(0.01) \\
A5& 4 & 114& 249& 11& 14& 8& 5& 0.35( 0.28)&0.25(0.16)\\
A6& 5 & 488& 1394& 18& 20& 12& 6& 6.78( 4.39)&4.33(2.37)\\
A7& 6 & 4073& 14800& 28& 29& 18& 7& 239.80( 139.40)&159.96(82.01)\\
A8& 7 & 25334& 111558& 41& 38& 24& 8& 5010.37( 2732.71)&3624(1867.85)\\
A9& 8 & 206444& 1080981& 58& 49& 32& 9&127978.46(67565.22) & (71404.29) \\
A10& 9 &$>$578435& - & - & - & - & - & - & - \\
\hline
%---------------------------------------------------------
%-- DmxDn 2x2 minors of a mxn matrix -------------------
%---------------------------------------------------------
D2x2& 3& 108& 222& 9& 10& 6& 3& 0.24( 0.20) & 0.23( 0.16) \\
D2x3& 5& 4488& 14184& 19& 20& 8& 3&171.74(97.48) & 124.06(71.02) \\
D3x3& 8& $>$257057& & & & & & & \\
\hline
HM &3&904&1546&52 &40 &5&345&96.72(35.80)&76.08(21.53)\\
\hline
\end{tabular}
\caption{\label{TIMING} TiGERS Timings }
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{9}
\bibitem[AGK]{AGK} B. Amrhein, O. Gloor and W. K\"uchlin,
On the walk, {\em Theoretical Computer Science} {\bf 187}
(1997) 179--202.
\bibitem[AF]{AF} D. Avis and K. Fukuda, A basis enumeration
algorithm for convex hulls and vertex enumeration of arrangements
and polyhedra, {\sl Discrete Computational Geometry} {\bf 8} (1992)
295--313.
\bibitem[AL]{AL} W.~W. Adams and P. Loustaunau,
{\sl An Introduction to Gr{\"o}bner Bases},
American Mathematical Society, 1994.
\bibitem[BM]{BM} D.~Bayer and I.~Morrison,
Standard bases and geometric invariant
theory I, {\sl Journal of Symbolic Computation} {\bf 6} (1988)
209--217.
\bibitem[BFS]{BFS}L.J.~Billera, P.~Filliman
and B.~Sturmfels, Constructions and complexity of
secondary polytopes, {\sl Advances in Mathematics} {\bf 83} (1990)
155--179.
\bibitem[CKM]{CKM} S.Collart, M.Kalkbrener and D.Mall, Converting
bases with the Gr\"obner walk, {\em Journal of Symbolic Computation}
{\bf 24} (1997) 465-469.
\bibitem[GKZ]{GKZ} I.M.~Gel'fand, M.~Kapranov and A.~Zelevinsky,
{\sl Multidimensional Determinants, Discriminants and Resultants},
Birkh\"auser, Boston, 1994.
\bibitem[CLO]{CLO} D. Cox, J. Little and D. O'Shea,
{\sl Ideals, Varieties, and Algorithms},
Springer-Verlag, New York, Second Edition, 1996.
\bibitem[Mac]{Mac} D.~Maclagan, Antichains of monomial ideals are
finite, {\sl Manuscript}, 1998.
\bibitem[MT]{MT} D.~Maclagan and R.~Thomas, On the combinatorics of
the toric Hilbert scheme, in preparation.
\bibitem[MR]{MR} T.~Mora and L.~Robbiano,
The Gr\"obner fan of an ideal,
{\sl Journal of Symbolic Computation} {\bf 6} (1988) 183--208.
\bibitem[PS]{PS} I.~Peeva and B.~Sturmfels,
Generic lattice ideals, Journal of the American Mathematical
Soceity {\bf 11} (1998) 363--373.
\bibitem[Stu]{Stu} B.~Sturmfels, Gr\"obner bases and Convex Polytopes,
{\em American Mathematical Society}, Providence, RI, 1995.
\bibitem[SST]{SST} M. Saito, B. Sturmfels and N. Takayama,
{\em Gr\"obner Deformations of Hypergeometric Differential Equations},
in preparation.
\bibitem[ST]{ST} B.~Sturmfels and R.~Thomas, Variation
of cost functions in integer programming, {\sl Mathematical Programming}
{\bf 77} (1997) 357-387.
\end{thebibliography}
\end{document}
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to tiger.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / TiGERS_0.9 / paper