\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}