[BACK]Return to tiger.tex CVS log [TXT][DIR] Up to [local] / OpenXM / src / Ti / paper

Annotation of OpenXM/src/Ti/paper/tiger.tex, Revision 1.1.1.1

1.1       maekawa     1: \documentclass[11pt]{article}
                      2: \oddsidemargin 0pt
                      3: \evensidemargin 0pt
                      4: \marginparwidth 40pt
                      5: \marginparsep 10pt
                      6: \topmargin 0pt
                      7: \headsep 10pt
                      8: \textheight 8.4in
                      9: \textwidth 6.5in
                     10: \renewcommand{\baselinestretch}{1.2}
                     11:
                     12: \begin{document}
                     13: \newtheorem{lemma}{Lemma}[subsection]
                     14: \newtheorem{theorem}[lemma]{Theorem}
                     15: \newtheorem{definition}[lemma]{Definition}
                     16: \newtheorem{observation}[lemma]{Observation}
                     17: \newtheorem{remark}[lemma]{Remark}
                     18: \newtheorem{corollary}[lemma]{Corollary}
                     19: \newtheorem{proposition}[lemma]{Proposition}
                     20: \newtheorem{example}[lemma]{Example}
                     21: \newtheorem{algorithm}[lemma]{Algorithm}
                     22:
                     23: \title{\bf Computing Gr\"obner Fans of Toric Ideals}
                     24: \author{Birkett Huber \\ \\
                     25: MSRI\\
                     26: 1000 Centennial Drive\\
                     27: Berkeley, CA 94720\\
                     28: {\tt birk@msri.org} \and
                     29: Rekha R. Thomas\\ \\
                     30: Dept. of Mathematics\\
                     31: Texas A \& M University\\
                     32: College Station, TX 77843\\
                     33: {\tt rekha@math.tamu.edu}}
                     34: \maketitle
                     35:
                     36: \begin{abstract}
                     37: The monomial initial ideals of a graded
                     38: polynomial ideal are in bijection with the vertices of a convex
                     39: polytope known as the state polytope of the ideal. The Gr\"obner fan
                     40: of the ideal is the normal fan of its state polytope.
                     41: In this paper we present a software system called TiGERS for computing
                     42: the Gr\"obner fan of a toric ideal by enumerating the edge graph of
                     43: its state polytope. The key contributions are an inexpensive algorithm
                     44: for local change of Gr\"obner bases in toric ideals and the
                     45: identification of a reverse search tree on the vertices of the state
                     46: polytope. Using these ideas we obtain a combinatorial Gr\"obner walk
                     47: procedure for toric ideals. TiGERS has been used to compute state
                     48: polytopes with over 200,000 vertices.
                     49: \end{abstract}
                     50:
                     51: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                     52: \section{Introduction}
                     53:
                     54: Consider the polynomial ring $k[{\bf x}] := k[x_1, \ldots, x_n]$ where
                     55: $k$ is a field and an ideal $I \subset k[{\bf x}]$ that is
                     56: homogeneous with respect to a positive grading $degree(x_i) =
                     57: \omega_i \in {\bf N} \backslash \{0\}$.
                     58: We use ${\bf N}$ to denote the set of non-negative integers. The
                     59: {\em initial ideal} of $I$ with respect to a {\em term order} $\succ$
                     60: on $k[{\bf x}]$ is the {\em monomial ideal} $in_{\succ}(I) := \langle
                     61: in_{\succ}(f) \, : \, f \in I \rangle$ where $in_{\succ}(f)$ is the
                     62: {\em initial term} of $f \in I$ with respect to $\succ$. The {\em
                     63: reduced Gr\"obner basis} of $I$ with respect to $\succ$ is the unique
                     64: finite set of monic polynomials   ${\cal G}_{\succ}(I) = \{g_1,
                     65: \ldots, g_t \} \subset I$ such that (i) $in_{\succ}(I) = \langle
                     66: in_{\succ}(g_1), \ldots, in_{\succ}(g_t) \rangle$ and (ii) for $i \neq j$,
                     67: no term of $g_i$ is divisible by $in_{\succ}(g_j)$. Reduced Gr\"obner
                     68: bases of polynomial ideals can be computed using {\em Buchberger's
                     69: algorithm}. See \cite{AL} or \cite{CLO} for further details.
                     70:
                     71: Given an arbitrary {\em weight vector} $c \in {\bf R}^n$, and a
                     72: polynomial $f = \sum k_{\alpha}x^{\alpha} \in k[{\bf x}]$, the
                     73: {\em initial term} of $f$ with respect to $c$ is defined to be the sum of all
                     74: terms $k_{\alpha}x^{\alpha}$ in $f$ such that the inner product
                     75: $c \cdot \alpha$ is maximal. The {\em initial ideal} of $I$ with
                     76: respect to $c$ is then $in_c(I) := \langle in_c(f) \, : \, f \in I
                     77: \rangle$. If $in_c(I)$ is a monomial ideal then $c$ is said to be
                     78: {\em generic} for $I$. It is known that for a term order $\succ$ on
                     79: $k[{\bf x}]$, there exists a weight vector $c \in {\bf N}^n$ such that
                     80: $in_c(I) = in_{\succ}(I)$. In this case we say that $c$ represents $\succ$
                     81: and it can be shown that $in_c(I) = in_{\succ}(I)$ if and only if
                     82: $in_c(g) = in_{\succ}(g)$ for each $g$ in ${\cal G}_{\succ}(I)$.
                     83:
                     84: Two weight vectors $c_1$ and $c_2$ in ${\bf R}^n$ are said to be
                     85: {\em equivalent modulo $I$} whenever $in_{c_1}(I) = in_{c_2}(I)$. The
                     86: set of all weight vectors that are equivalent to $c \in {\bf R}^n$ form
                     87: a relatively open polyhedral cone in ${\bf R}^n$, the closure of which
                     88: is called the {\em Gr\"obner cone} of $c$. The Gr\"obner cone of $c$
                     89: is $n$-dimensional if and only if $c$
                     90: is generic for $I$. The collection of all Gr\"obner cones
                     91: of $I$ form a {\em polyhedral fan} in ${\bf
                     92: R}^n$ called the {\em Gr\"obner fan} of $I$ \cite{MR}. Since $I$ is
                     93: homogeneous with respect to a positive grading,
                     94: this fan is, in fact, {\em complete} (i.e., covers ${\bf R}^n$) and
                     95: further, each Gr\"obner cone of $I$ contains a strictly positive vector
                     96: of ${\bf R}^n$.
                     97:
                     98: The Gr\"obner fan of $I$ is the {\em normal fan} of a polytope in
                     99: ${\bf R}^n$ called the {\em state polytope} of $I$ \cite{BM}, denoted
                    100: as $St(I)$. Therefore, $I$ has only
                    101: finitely many distinct reduced Gr\"obner bases as $c$ varies over
                    102: all weight vectors in ${\bf R}^n$. (See \cite{Mac} for a new proof.)
                    103: The faces of $St(I)$ are
                    104: in bijection with the distinct initial ideals of $I$, with the
                    105: vertices of $St(I)$ corresponding bijectively to the distinct monomial
                    106: initial ideals of $I$. The distinct monomial initial ideals of $I$, in turn,
                    107: are in bijection with the distinct reduced Gr\"obner bases of $I$
                    108: obtained from term orders. Hence,
                    109: computing all such initial ideals amounts to searching the {\em edge graph}
                    110: of $St(I)$. Two monomial initial ideals $in_{c_1}(I)$ and
                    111: $in_{c_2}(I)$ are said to be {\em adjacent} if
                    112: the corresponding vertices of $St(I)$ are adjacent or equivalently, if
                    113: the Gr\"obner cones of the generic weight vectors $c_1$ and $c_2$ share a
                    114: common {\em facet}. See
                    115: Chapters 1-3 in \cite{Stu} for proofs of the results quoted above
                    116: and a full discussion of Gr\"obner fans and state polytopes of graded
                    117: polynomial ideals. Algorithms for their construction are also included.
                    118:
                    119: Given a matrix $A = [a_1, \ldots, a_n] \in {\bf Z}^{d \times n}$ of
                    120: rank $d$, the {\em toric ideal} of $A$, denoted as $I_A$, is the
                    121: kernel of the homomorphism $k[x_1,\ldots,x_n]
                    122: \rightarrow k[t_1^{\pm 1}, \ldots, t_d^{\pm 1}]$, such that $x_j
                    123: \mapsto t^{a_j}$ (see Chapter 4 in \cite{Stu}). The ideal $I_A$ is a
                    124: $d$-dimensional prime ideal that is
                    125: generated by the {\em binomials} $x^{u^+} - x^{u^-}$ where $u = u^+ -
                    126: u^-$ lies in the $(n-d)$-dimensional saturated lattice $ker_{\bf Z}(A):=
                    127: \{ u \in {\bf Z}^n : Au = 0 \}$. Here $u^- = (-u)^+$ and $u^+$ is
                    128: defined as $u^+_i = u_i$ if $u_i > 0$ and $u^+_i = 0$ otherwise. Hence
                    129: $u^+, u^- \in {\bf N}^n$. The mechanics of the Buchberger algorithm ensure
                    130: that every reduced Gr\"obner basis of $I_A$ again consists of finitely
                    131: many binomials of the above type. We will assume that $ker_{\bf Z}(A)
                    132: \cap {\bf N}^n  = \{0\}$ which guarantees a positive integral vector
                    133: $\omega$ in the row space of $A$. Then $I_A$ is homogeneous
                    134: with respect to the grading $degree(x_i) = \omega_i$.
                    135:
                    136: Let ${\cal G}_c = \{x^{\alpha_i} -
                    137: x^{\beta_i} \, : \, i = 1, \ldots, t \}$ be the reduced Gr\"obner
                    138: basis of $I_A$ with respect to a generic weight vector $c \in {\bf
                    139: R}^n$. (The positive term of a binomial in ${\cal G}_c$ is always
                    140: assumed to be the initial term with respect to $c$.) The Gr\"obner
                    141: cone of $c$ is then the $n$-dimensional polyhedral cone
                    142: $ {\cal K}_c := \{ u \in {\bf R}^n : \alpha_i \cdot u \geq \beta_i
                    143: \cdot u, \, i = 1, \ldots, t \}$
                    144: whose lineality space (${\cal K}_c \cap -{\cal K}_c$)
                    145: is the row space of $A$. We may assume that $c$ is a strictly positive
                    146: integral vector since
                    147: ${\cal K}_c$ is a rational cone and $\omega \in {\cal K}_c$. Further,
                    148: $c'$ is equivalent to $c$ if and only if
                    149: $in_{c'}(x^{\alpha_i} - x^{\beta_i}) = x^{\alpha_i}$ for each binomial
                    150: $x^{\alpha_i} - x^{\beta_i} \in {\cal G}_c$. State polytopes and
                    151: Gr\"obner fans of toric ideals were studied in \cite{ST}. This paper
                    152: gives several custom-tailored construction methods for these entities
                    153: when the ideal is toric.
                    154:
                    155: The Gr\"obner fan of $I_A$ has various applications: In \cite{ST} it
                    156: was used as a model for {\em sensitivity analysis} for the family
                    157: of {\em integer programs} $min \{ c \cdot x \, :\, Ax = b, \, x \in
                    158: {\bf N}^n \}$ as $b$ varies in ${\bf Z}^d$ and $c$ in ${\bf R}^n$.
                    159: The {\em secondary fan} of $A$ \cite{BFS}, \cite{GKZ} is a coarsening
                    160: of the Gr\"obner fan of $I_A$ (see Chapter 8 in \cite{Stu}). This fan has
                    161: important applications to problems in discrete geometry. In between
                    162: the secondary fan and the Gr\"obner fan of $A$ lives the {\em
                    163: hypergeometric fan} of $A$ which has been used for studying
                    164: $A$-{\em hypergeometric} differential equations using
                    165: {\em Gr\"obner deformations}
                    166: \cite{SST}. Both these coarser fans can be obtained from the Gr\"obner
                    167: fan of $I_A$. Finally, the {\em Gr\"obner walk} procedure introduced in
                    168: \cite{CKM} uses the Gr\"obner fan for Gr\"obner basis conversions.
                    169:
                    170: \begin{example}\label{EX1}
                    171: Let $A := \left( \begin{array}{ccccc}
                    172:          1 & 1 & 1 & 1 & 1 \\
                    173:          0 & 1 & 2 & 1 & 0 \\
                    174:          0 & 0 & 1 & 2 & 1
                    175: \end{array} \right )$. For ease of exposition we associate the
                    176: variables $a,b,c,d,e$ to the five columns of $A$ and consider the
                    177: toric ideal $I_A \subset k[a,b,c,d,e]$. This ideal
                    178: yields eight distinct monomial initial ideals. The state polytope
                    179: $St(I_A)$ is an
                    180: octagon in ${\bf R}^5$ and the Gr\"obner fan of $I_A$ can be drawn in
                    181: ${\bf R}^2$ after moding out the row space of $A$ from each Gr\"obner
                    182: cone. Figure \ref{FIG1} shows a schematic representation of the resulting {\em
                    183: pointed} Gr\"obner fan of $I_A$. Each maximal cone is labeled by the
                    184: reduced Gr\"obner basis induced by the weight vectors in the
                    185: interior of that cone. The binomials in
                    186: a reduced Gr\"obner basis that contribute the facet inequalities of
                    187: its Gr\"obner cone are marked with dots. Notice that for two adjacent
                    188: reduced Gr\"obner bases, their common facet binomial $x^{\alpha} -
                    189: x^{\beta}$ appears in both reduced Gr\"obner bases with
                    190: $x^{\alpha}$ as initial term in one basis and $x^{\beta}$ as
                    191: initial term in the other.
                    192: \end{example}
                    193:
                    194: \begin{figure}[h]
                    195: \fbox{
                    196: \setlength{\unitlength}{1.7cm}
                    197: \begin{picture}(9,6)
                    198:  \put(0,2.1){
                    199:     \makebox(1.8,1.2){  %G1
                    200:            $\begin{array}{ll}
                    201:                 \bullet & a^2c-b^2e\\
                    202:                         & a^2d-be^2\\
                    203:                 \bullet & bd-ce
                    204:              \end{array}$ }}
                    205:
                    206:   \put(0.2,4.3){
                    207:     \makebox(1.8,1.2){ %G2
                    208:            $\begin{array}{ll}
                    209:                \bullet& b^2e-a^2c\\
                    210:                \bullet& a^2d-be^2\\
                    211:                       &bd-ce\\
                    212:              \end{array}$ }}
                    213:  \put(3.4,4.5){%G4
                    214:     \makebox(1.8,1.5){
                    215:            $\begin{array}{ll}
                    216:              \bullet & a^2d^2-ce^3\\
                    217:                      & b^2e-a^2c\\
                    218:              \bullet & be^2-a^2d\\
                    219:                      & bd-ce
                    220:              \end{array}$ }}
                    221:  \put(6.4,4.4){ %G6
                    222:     \makebox(1.8,1.6){
                    223:            $\begin{array}{ll}
                    224:              \bullet & ce^3-a^2d^2\\
                    225:                      & b^2e-a^2c\\
                    226:                      & be^2-a^2d\\
                    227:              \bullet & bd-ce
                    228:              \end{array}$ }}
                    229: \put(7.2,2.2){  %G8
                    230:     \makebox(1.8,1.5){
                    231:            $\begin{array}{ll}
                    232:              \bullet & b^3d-a^2c^2 \\
                    233:                      & b^2e-a^2c\\
                    234:                      & be^2-a^2d\\
                    235:              \bullet & ce-bd
                    236:              \end{array}$ }}
                    237: \put(6.4,0.4){  %G7
                    238:     \makebox(1.8,1.4){ %G4
                    239:            $\begin{array}{ll}
                    240:              \bullet & a^2c^2-b^3d\\
                    241:              \bullet & b^2e-a^2c\\
                    242:                      &  be^2-a^2d\\
                    243:                      &  ce-bd
                    244:              \end{array}$ }}
                    245: \put(3.4,0){
                    246:     \makebox(1.8,1.2){ %G5
                    247:            $\begin{array}{ll}
                    248:             \bullet & a^2c-b^2e\\
                    249:             \bullet & be^2-a^2d\\
                    250:                     & ce-bd
                    251:              \end{array}$ }}
                    252: \put(1.0,0.6){
                    253:     \makebox(0.2,0.2){ %G3
                    254:            $\begin{array}{ll}
                    255:                       & a^2c-b^2e\\
                    256:               \bullet & a^2d-be^2\\
                    257:               \bullet & ce-bd\\
                    258:              \end{array}$ }}
                    259:
                    260:  \put(4.5,3){\line( 1,2 ){1.5}}
                    261:  \put(4.5,3){\line( 1,-2){1.5}}
                    262: \put(4.5,3){\line( -3,4 ){2.25}}
                    263:  \put(4.5,3){\line( -2,-3){2}}
                    264:  \put(4.5,3){\line( -4,1 ){4.5}}
                    265:  \put(4.5,3){\line( -3,-1){4.5}}
                    266:  \put(4.5,3){\line( 4,1 ){4.5}}
                    267:  \put(4.5,3){\line( 3,-1){4.5}}
                    268: \end{picture}
                    269: }
                    270: \caption{\label{FIG1}A schematic of the Gr\"obner fan in Example \ref{EX1}}
                    271: \end{figure}
                    272:
                    273: In this paper we introduce a software system called TiGERS for computing the
                    274: Gr\"obner fan of a toric ideal.
                    275: The program searches the edge graph of the state polytope $St(I_A)$ to find all
                    276: the distinct monomial initial ideals (reduced Gr\"obner bases) of $I_A$.
                    277: This search can be done in two ways: For moderate
                    278: sized examples, the graph is searched by a breadth-first search strategy
                    279: on the entire edge-graph of $St(I_A)$. This approach needs to maintain
                    280: and search the list of all Gr\"obner bases found. When $St(I_A)$ is too
                    281: large this approach will bog down and we use a {\em reverse search technique}\/
                    282: instead. This involves a depth-first search
                    283: on a subgraph of the edge graph of $St(I_A)$ called the reverse search tree,
                    284: and can be implemented so that no more than one Gr\"obner basis ever
                    285: needs to be stored.
                    286: In Section 2 we give an overview of the main algorithm in
                    287: TiGERS and describe the reverse search procedure.
                    288: These ideas allow {\em
                    289: combinatorial Gr\"obner walks} in toric ideals.
                    290: For each reduced Gr\"obner basis found,
                    291: the algorithm does two main local computations. The first is to
                    292: determine all the facets of that Gr\"obner cone and the
                    293: second is to determine an adjacent Gr\"obner basis to the
                    294: current one. In Section 3 we give an algorithm for
                    295: local change of Gr\"obner bases in toric ideals based on
                    296: \cite{CKM}. Unlike usual local change
                    297: algorithms, our procedure does not require any weight vectors to be
                    298: computed. We then discuss some special tricks
                    299: to find the facets of a fixed Gr\"obner cone in the case of toric
                    300: ideals. Section 4 reports computational experience with TiGERS.
                    301:
                    302: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                    303:
                    304: \section{The main algorithm in TiGERS}
                    305:
                    306: Let ${\cal G}_c = \{ x^{\alpha_i} - x^{\beta_i}, \, i = 1,
                    307: \ldots, t \}$ be the reduced Gr\"obner basis of $I_A$ with respect to
                    308: the generic weight vector $c \in {\bf R}^n$.
                    309: An inequality $\alpha_k \cdot u \geq
                    310: \beta_k \cdot u$, $k \in \{1,\ldots,t\}$ is irredundant for the
                    311: Gr\"obner cone ${\cal K}_c = \{ u \in {\bf R}^n \, : \, \alpha_i \cdot
                    312: u \geq \beta_i \cdot u, \, i = 1, \ldots, t \}$ if the relaxed cone
                    313: $\{ u \in {\bf R}^n \, : \, \alpha_i \cdot u \geq \beta_i \cdot u, \,
                    314: i = 1, \ldots, t, i \neq k \}$ properly contains ${\cal K}_c$. If
                    315: $\alpha_k \cdot u \geq \beta_k \cdot u$ is irredundant for ${\cal
                    316: K}_c$ then ${\cal K}_c \cap \{u \in {\bf R}^n \, : \, \alpha_k \cdot u
                    317: = \beta_k \cdot u \}$ is called a {\em facet} of ${\cal K}_c$ and
                    318: $x^{\alpha_k} - x^{\beta_k}$ is a {\em facet binomial} of ${\cal G}_c$.
                    319:
                    320: \begin{lemma}\cite{ST} \label{facets}
                    321: The binomial $x^{\alpha_k} - x^{\beta_k} \in {\cal
                    322: G}_c$ is a facet binomial of ${\cal G}_c$ if and only if
                    323: the linear system $\{u \in {\bf R}^n : \alpha_i \cdot u \geq \beta_i
                    324: \cdot u \,, \, i = 1,\ldots,t,\, i \neq k \} \cup
                    325: \{ u \in {\bf R}^n : \beta_k \cdot u \geq \alpha_k \cdot u \}$ is feasible.
                    326: \end{lemma}
                    327:
                    328: Therefore, all facets of the Gr\"obner cone ${\cal K}_c$ can be found
                    329: by checking the feasibility of  $t$ systems of linear inequalities,
                    330: which in turn can be done by linear programming.
                    331: In practice this can be computationally expensive when $t$ is large
                    332: and we discuss certain speed ups in Section 3.2.
                    333:
                    334: Suppose $x^{\alpha} - x^{\beta}$ is a
                    335: facet binomial of ${\cal G}_c$
                    336: such that $in_c(x^{\alpha} - x^{\beta}) = x^{\alpha}$ and ${\cal G}_{c'}$
                    337: be adjacent to ${\cal G}_c$ with $in_{c'}(x^{\alpha} - x^{\beta})
                    338: = x^{\beta}$. In order to compute the edge graph of $St(I_A)$,
                    339: we require a subroutine to make a local change of reduced
                    340: Gr\"obner bases from ${\cal G}_c$ to ${\cal G}_{c'}$ through the facet
                    341: given by $x^{\alpha} - x^{\beta}$. We use ${flip({\cal G}_c, x^{\alpha} -
                    342: x^{\beta})}$ to denote both the subroutine that yields ${\cal G}_{c'}$
                    343: from ${\cal G}_c$ as well as the reduced Gr\"obner basis
                    344: ${\cal G}_{c'}$ that results from the ``flip''. In Section 3.1 we
                    345: describe the precise local change algorithm in TiGERS.
                    346:
                    347: \begin{remark}{\em
                    348: If $x^{\alpha} - x^{\beta}$ lies in the reduced Gr\"obner basis of a
                    349: toric ideal, then the supports of $\alpha$ and $\beta$ are disjoint.
                    350: This guarantees that each facet in a toric Gr\"obner cone corresponds
                    351: to precisely one binomial in the corresponding Gr\"obner basis.
                    352: However, this is not true for general homogeneous
                    353: binomial ideals. Consider $J = \langle
                    354: b^3d-b^2ce, a2c-b2e, bcd-c2e \rangle$. Under the reverse lexicographic
                    355: order $a \succ c \succ d \succ e \succ b$, its reduced Gr\"obner basis is
                    356: $G = \{ ceb^2-db^3, c^2e-cdb, a^2db^3-e^2b^4, a^2c-eb^2 \}$. The
                    357: inequality $u_3 + u_5 \geq u_2 + u_4$ is a facet inequality of the
                    358: Gr\"obner cone of $G$. For $\omega$ in the relative interior of this facet,
                    359: we get both $in_{\omega}(ceb^2-db^3) = ceb^2-db^3$ and
                    360: $in_{\omega}(c^2e-cdb) = c^2e-cdb$.}
                    361: \end{remark}
                    362:
                    363: \begin{algorithm}
                    364:  Enumerating the edge graph of $St(I_A)$ via breadth-first search.
                    365: \begin{tabbing}
                    366:  xx\=xx\=xx\=xx\=\kill
                    367:    {\bf Input:} Any reduced Gr\"obner basis ${\cal G}_0$ of $I_A$.\\
                    368:    {\bf Output:} All reduced Gr\"obner bases of $I_A$ (all vertices of
                    369:                  $St(I_A)$).\\
                    370:   \>{\tt Todo} := $\left[{\cal G}_0\right]$; \\
                    371:   \>{\tt Verts} := $\left[ \,\, \right]$;\\
                    372:    \> While(${\tt Todo}$ not empty) do\\
                    373:    \> \> ${\cal G}$ := first-element-in({\tt Todo});\\
                    374:    \> \> Remove ${\cal G}$ from {\tt Todo};\\
                    375:    \> \> add ${\cal G}$ to {\tt Verts};\\
                    376:    \> \> determine list $L$ of facet binomials of ${\cal G}$\\
                    377:    \> \> for each $x^{\alpha} - x^{\beta}$ in $L$ do\\
                    378:    \> \> \> Compute $G'=flip({\cal G},x^{\alpha}-x^{\beta})$\\
                    379:  %  \>\>\> If ${\cal G}'$ not in {\tt Todo} or {\tt Verts} then
                    380:  %         add ${\cal G}'$ to the beginning of the list {\tt Todo};\\
                    381:    \>\>\> If ${\cal G}'\not\in {\tt Todo}\cup{\tt Verts}$ then
                    382:           add ${\cal G}'$ to {\tt Todo};\\
                    383:    \>\>End \\
                    384:    \>End\\
                    385:    \> output {\tt Verts}
                    386: \end{tabbing}
                    387: \end{algorithm}
                    388:
                    389: This algorithm works well in practice but does have the drawback that all
                    390: vertices must be stored, and that every time a vertex is visited it must
                    391: be checked against all other vertices seen thus far in order to
                    392: determine if it is indeed a new vertex. The storage and search
                    393: costs involved in this procedure can become prohibitive as the size of
                    394: $St(I_A)$ increases. As an example consider
                    395: $A := \left( \begin{array}{ccccccccc}
                    396:          3 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\
                    397:          0 & 1 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\
                    398:          0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 3
                    399: \end{array} \right )$. The ideal $I_A$ involves only nine variables
                    400: and most reduced Gr\"obner bases of this ideal have fewer than
                    401: $36$ elements each of degree no greater than seven. Yet, $St(I_A)$ has
                    402: $54,828$ vertices and our breadth first search algorithm was exhausting
                    403: a personal computer with 64 kilobytes of memory before getting through about
                    404: $13,000$ vertices. In order to push this calculation through we
                    405: resorted to the reverse enumeration paradigm of Avis and Fukuda
                    406: \cite{AF}. The basic idea there is to do a depth first search on a directed
                    407: subgraph of $St(I_A)$.
                    408:
                    409: We say that a polynomial $f \in k[{\bf x}]$ is {\em marked} by a
                    410: term order $\succ$ on $k[{\bf x}]$, if the initial term of $f$
                    411: with respect to $\succ$ has been distinguished from among all terms in
                    412: $f$. A polynomial $f$ that has been marked with respect to $\succ$ is
                    413: said to be {\em mismarked} with respect to $\succ'$,
                    414: if $in_{\succ}(f) \neq in_{\succ'}(f)$.
                    415:
                    416: \begin{lemma} \label{marking}
                    417: Let ${\cal G}_{\succ}$ be the reduced Gr\"obner basis of $I_A$ with respect
                    418: to the term order $\succ$. Then for a term order $\succ' \neq
                    419: \succ$, the reduced Gr\"obner basis ${\cal G}_{\succ'}$ equals ${\cal
                    420: G}_{\succ}$ if and only if no facet
                    421: binomial of ${\cal G}_{\succ}$ is mismarked with respect to $\succ'$.
                    422: \end{lemma}
                    423:
                    424: \noindent{\em Proof:} Suppose no facet binomial of ${\cal G}_{\succ}$
                    425: is mismarked with respect to $\succ'$ and let $c'$ be a weight vector
                    426: from the interior of the Gr\"obner cone ${\cal K}_{\succ'}$. Then for
                    427: each facet binomial $x^{\alpha} - x^{\beta}$ in ${\cal G}_{\succ}$, we
                    428: have $c' \cdot \alpha > c' \cdot \beta$
                    429: which implies that $c'$ lies in the interior of the Gr\"obner cone
                    430: ${\cal K}_{\succ}$. Hence ${\cal K}_{\succ'} = {\cal K}_{\succ}$ which
                    431: implies that ${\cal G}_{\succ} = {\cal G}_{\succ'}$. Conversely, if
                    432: ${\cal G}_{\succ} = {\cal G}_{\succ'}$, then no binomial in ${\cal
                    433: G}_{\succ}$ is mismarked with respect to $\succ'$.
                    434:
                    435: \begin{definition} \label{def-tree}
                    436: For a given term order $\succ$ we define the
                    437: {\em reverse search tree $T_\succ(I_A)$} as follows:\\
                    438: The vertices of $T_{\succ}(I_A)$ are the vertices of $St(I_A)$
                    439: (i.e. the various reduced Gr\"obner bases of $I_A$ arising
                    440: from term orders). For two reduced Gr\"obner bases ${\cal G}_i$ and
                    441: ${\cal G}_j$, $[{\cal G}_i,{\cal G}_j]$ directed from
                    442: ${\cal G}_i$ to ${\cal G}_j$ is an edge of
                    443: $T_\succ(I_A)$ if ${\cal G}_j$ is obtained from ${\cal G}_i$ by the
                    444: subroutine $flip({\cal G}_i,x^{\alpha} - x^{\beta})$ where $x^{\alpha} -
                    445: x^{\beta}$ is the unique facet binomial of ${\cal G}_i$
                    446: whose leading term is lexicographically maximal
                    447: among all facet binomials of ${\cal G}_i$ that are mismarked with
                    448: respect to $\succ$.
                    449: \end{definition}
                    450:
                    451: %The following theorem proves that $T_\succ(I_A)$ is indeed a tree.
                    452:
                    453: \begin{theorem}
                    454: The reverse search tree $T_\succ(I_A)$ is an acyclic directed graph
                    455: with a unique sink.
                    456: \end{theorem}
                    457:
                    458: \noindent{\em Proof:}
                    459: By Lemma~\ref{marking} each reduced Gr\"obner basis ${\cal G}$ of
                    460: $I_A$ (vertex of $St(I_A)$) except ${\cal G}_\succ$ has at least one
                    461: mismarked facet binomial with respect to $\succ$. By the definition of
                    462: $T_\succ(I_A)$, each such ${\cal G}$ has a unique adjacent
                    463: reduced Gr\"obner basis given by $flip({\cal G},x^{\alpha} -
                    464: x^{\beta})$ where $x^{\alpha} - x^{\beta}$ is the unique facet
                    465: binomial of ${\cal G}$ whose leading term is lexicographically maximal
                    466: among all mismarked facet binomials of ${\cal G}$. Therefore
                    467: $T_\succ(I_A)$ is a directed graph such that the
                    468: out-degree of ${\cal G}_{\succ}$ in $T_\succ(I_A)$ is zero and of all
                    469: other reduced Gr\"obner bases is one.
                    470:
                    471: Suppose there was a cycle $C = (v_1, \ldots, v_l)$ of length $l$ in
                    472: $T_\succ(I_A)$ where vertex $v_i$ corresponds to the reduced
                    473: Gr\"obner basis ${\cal G}_i$ of $I_A$ and $v_{l+1} = v_1$ and
                    474: ${\cal G}_{l+1} = {\cal G}_1$. If $x^{\alpha_i}-x^{\beta_i}$ is
                    475: the common facet binomial of ${\cal G}_i$ and ${\cal G}_{i+1}$ with
                    476: $x^{\alpha_i}$ the leading term with respect to ${\cal G}_i$ and
                    477: $x^{\beta_i}$ the leading term with respect to ${\cal G}_{i+1}$
                    478: for $i=1,\ldots,l$, then $v_{i+1} - v_i =
                    479: \beta_i - \alpha_i$ for $i=1,\ldots, l$. Since $C$ is a cycle in
                    480: $T_\succ(I_A)$ we get $(\beta_1 - \alpha_1) + (\beta_2 -
                    481: \alpha_2) + \cdots + (\beta_l - \alpha_l) = 0$. However, each binomial
                    482: $x^{\alpha_i}-x^{\beta_i}$ for $i=1,\ldots,l$ is mismarked with
                    483: respect to $\succ$ which implies that for a weight vector $c$
                    484: representing $\succ$ we have, $c \cdot (\beta_i - \alpha_i) > 0$.
                    485: This leads to the contradiction
                    486: $0 = c \cdot
                    487: \sum_{i=1}^{l} ({\beta_i}-{\alpha_i}) = \sum_{i=1}^{l}
                    488: c \cdot (\beta_i - \alpha_i) > 0 $.
                    489:
                    490: \begin{corollary}\label{unique-path}
                    491: From any reduced Gr\"obner basis ${\cal G}_c$ of $I_A$ there is a
                    492: unique path in the reverse search tree $T_\succ(I_A)$ to the sink
                    493: ${\cal G}_\succ$.
                    494: \end{corollary}
                    495:
                    496: Corollary~\ref{unique-path} proves that toric ideals admit
                    497: combinatorial Gr\"obner walks that can be used for converting one
                    498: reduced Gr\"obner basis of $I_A$ into another. Given any reduced
                    499: Gr\"obner basis ${\cal G}$ of $I_A$ and any term order $\succ$, we can
                    500: move from ${\cal G}$ to ${\cal G}_\succ$ by tracing the unique path in the
                    501: reverse search tree $T_\succ(I_A)$ from ${\cal G}$ to ${\cal G}_\succ$.
                    502: Unlike in the usual Gr\"obner walk procedure \cite{CKM},\cite{AGK}
                    503: to convert one Gr\"obner basis into another there are no explicit cost
                    504: vectors involved in these walks. These combinatorial walks also have
                    505: the advantage that there is never the danger of walking through a
                    506: lower dimensional face of a Gr\"obner cone thus eliminating several
                    507: numerical considerations that otherwise have to be dealt with. The
                    508: trade off is that at every vertex of the state polytope, all facets of
                    509: the current Gr\"obner cone have to be computed which can be highly
                    510: non-trivial for general ideals, but is relatively easy for toric ideals.
                    511:
                    512:
                    513: \begin{algorithm}
                    514:  Enumerating the edge graph of $St(I_A)$ via reverse search.
                    515: \begin{tabbing}
                    516:  xx\=xx\=xx\=xx\=xx\=\kill
                    517:    {\bf Input:} A reduced Gr\"obner basis ${\cal R}_\succ$ of $I_A$ and its
                    518:                 term order $\succ$.\\
                    519:    {\bf Output:} All reduced Gr\"obner bases of $I_A$ (all vertices of
                    520: $St(I_A)$).\\
                    521:    \> set ${\cal G} := {\cal R}_\succ$; j:=0 ; L := list of facet binomials of ${\cal G}$ which are marked by $\succ$\\
                    522:    \> output ${\cal G}$\\
                    523:    \> repeat \\
                    524:    \> \> while $j < |L|$ do \\
                    525:    \> \> \> $j := j + 1$.\\
                    526:    \> \> \> ${\cal G}':=flip({\cal G},L[j])$;\\
                    527:    \> \> \> if [${\cal G}'$,${\cal G}$] in $T_{\succ}(I_A)$ then\\
                    528:    \> \> \> \> ${\cal G}$:= {\cal G}'; $j := 0$; L := list of facets of
                    529:                ${\cal G}$ marked by $\succ$ \\
                    530:    \> \> \> \> output ${\cal G}$\\
                    531:    \> \> \>  endif\\
                    532:    \> \> endwhile\\
                    533:    \> \> If ${\cal G} \neq {\cal R}_{\succ}$ then\\
                    534:    \> \> \> ${\cal G}'$ := unique element such that [${\cal G}$,${\cal G}'$]
                    535:             in $T_{\succ}(I_A)$;
                    536:             $j:=0$; L := list of facets of ${\cal G}'$ marked by $\succ$\\
                    537:    \> \> \>repeat $j:=j+1$ until the common facet of ${\cal G}$ and ${\cal G'}$
                    538:            is the $j$th facet of $L$.\\
                    539:    \> \> \> ${\cal G}$ := ${\cal G}'$\\
                    540:    \> \> endif\\
                    541:    \> until ${\cal G} = {\cal R}_{\succ}$ and $j = |L|$.
                    542: \end{tabbing}
                    543: \end{algorithm}
                    544:
                    545: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                    546:
                    547: \section{Local Computations}
                    548:
                    549: Having given an overview of the algorithm in TiGERS for computing the
                    550: Gr\"obner fan of a toric ideal, we now focus on the computations
                    551: that have to be made at a fixed reduced Gr\"obner basis encountered
                    552: while searching the edge graph of $St(I_A)$. The two main issues here
                    553: are (i) how to compute a Gr\"obner basis that shares a prescribed
                    554: facet binomial with the current basis and (ii) how to compute all the
                    555: facets of a toric Gr\"obner cone.
                    556:
                    557: \subsection{Local change of Gr\"obner bases in toric ideals}
                    558:
                    559: \begin{algorithm} Local change of reduced Gr\"obner bases in $I_A$.\\
                    560: (a specialization of \cite{CKM} and Subroutine 3.7 in \cite{Stu}).
                    561: \label{localchange}
                    562: \end{algorithm}
                    563: \noindent{\bf Input:} (i) A reduced Gr\"obner basis ${\cal G} =\{
                    564: {\underline x^{a_k}}-x^{b_k} :  k = 1,..,t \}$ of $I_A$.\\
                    565: (The weight vector inducing ${\cal G}$ is generic and the underlined terms
                    566: are the leading terms.)\\
                    567: (ii) A prescribed facet binomial ${\underline x^{a_i}} - x^{b_i}$ of ${\cal G}$.\\
                    568: \noindent{\bf Output:} The reduced Gr\"obner basis adjacent to ${\cal
                    569: G}$ in which ${\underline x^{b_i}} - x^{a_i}$ is a facet binomial.
                    570: \vskip .2cm
                    571:
                    572: \indent \indent \indent a. Let $Old :=
                    573: \{{\underline x^{a_i}}-x^{b_i}\} \cup \{{\underline x^{a_j}} \, : \,
                    574:             {\underline x^{a_j}}-x^{b_j} \in {\cal G},\, j \neq i \}$.\\
                    575: \indent \indent \indent b. Let $Temp$ be got from
                    576: $Old$ by switching the marking on {\bf the} binomial in $Old$.\\
                    577: \indent \indent \indent \indent i.e.,
                    578: $Temp := \{ {\underline x^{b_i}}-x^{a_i} \} \cup
                    579: \{{\underline x^{a_j}} \, : \, x^{a_j} \in Old \}$. \\
                    580: \indent \indent \indent c. Compute the reduced Gr\"obner basis
                    581: of $Temp$ with respect to the new marking.
                    582: \indent \indent \indent \indent Store the (marked)
                    583: result in $New$.\\
                    584: \indent \indent \indent d. Set ${\cal G}' := \emptyset$\\
                    585: \indent \indent \indent e. For each $h$ in $New$ DO\\
                    586: \indent \indent \indent \indent (i) Reduce $h$ to zero modulo
                    587: $Old$ keeping track of the coefficients during reduction.
                    588: \indent \indent \indent \indent \indent This gives the representation
                    589: \[ h = \sum_{g \in Old} p_g \cdot g \]
                    590: \indent \indent \indent \indent (ii) Compute the polynomial
                    591: \[ \sum_{full(g) \in {\cal G}} p_g \cdot full(g) \]
                    592: \indent \indent \indent \indent \indent and add it to the set ${\cal G}'$.
                    593: ($full(g) \in {\cal G}$ is the completion of $g \in Old$.)\\
                    594: \indent \indent \indent f. Auto-reduce ${\cal G}'$ with respect
                    595: to the markings in $New$ to get ${\cal G}_{new}$. \\
                    596: Then ${\cal G}_{new}$ is the reduced Gr\"obner
                    597: basis adjacent to ${\cal G}$ such that ${\underline x^{a_i}} -
                    598: x^{b_i}$ is a facet binomial in ${\cal G}$ and ${\underline x^{b_i}} -
                    599: x^{a_i}$ is a facet binomial in ${\cal G}_{new}$.\\
                    600:
                    601: \noindent {\sl Proof of correctness:} Let ${\cal K}$ and ${\cal
                    602: K}_{new}$ be the Gr\"obner cones of ${\cal G}$ and ${\cal G}_{new}$
                    603: respectively. The linear span of the common facet of
                    604: ${\cal K}$ and ${\cal K}_{new}$ is $\{u \in {\bf R}^n : a_i \cdot u
                    605: = b_i \cdot u \}$. Let $c_1 \in interior({\cal K})$,
                    606: $c_2 \in interior({\cal K}_{new})$ and $c$ be a vector in the relative
                    607: interior of $K \cap K_{new}$. By definition, $Old = in_c({\cal G}) :=
                    608: \{ in_c(f) : f \in {\cal G} \}$
                    609: and with respect to the markings specified in Step a, $Old$ is the
                    610: reduced Gr\"obner basis of $in_c(I_A)$ with respect to $c_1$. Since
                    611: $Temp$ is got from $Old$ by simply reversing the marking on the facet
                    612: binomial $x^{a_i} - x^{b_i}$, $Temp$ is a generating set for $in_c(I_A)$.
                    613:
                    614: We first show that the set $New$ computed in Step c, using $Temp$ as
                    615: input, is the reduced Gr\"obner basis of $in_c(I_A)$ with respect to
                    616: $c_2$. Clearly the marked monomials in $Temp$ are
                    617: their own initial terms with respect to $c_2$. The non-trivial $S$-pair
                    618: computations in Step c are those between a monomial $x^{a_j}$,\, $j
                    619: \neq i$, and the
                    620: binomial ${\underline x^{b_i}}-x^{a_i}$. This results in a monomial
                    621: which either reduces to zero with respect to the current partial
                    622: Gr\"obner basis or reduces to a monomial that gets added to the
                    623: current partial Gr\"obner basis. There is no point during this process
                    624: at which an unmarked  binomial is produced that is required to be marked.
                    625: No binomials are produced during such an $S$-pair
                    626: reduction either. Hence all subsequent $S$-pair computations are
                    627: also of the above nature and so in fact, the set $New$ is as
                    628: claimed above and consists of the binomial ${\underline
                    629: x^{b_i}}-x^{a_i}$ along with monomials some of which were possibly
                    630: produced during the Buchberger process. Steps d and e simply lift
                    631: $New$ to a minimal Gr\"obner basis ${\cal G'}$ of $I_A$ with respect
                    632: to $c_2$. Finally, Step f auto-reduces this minimal Gr\"obner basis
                    633: to the reduced Gr\"obner basis ${\cal G}_{new}$ of $I_A$ with
                    634: respect to $c_2$. \\
                    635:
                    636: The most important computational advantage of the above local change
                    637: algorithm is that it does not require the computation of a weight
                    638: vector in the interior of ${\cal K}_{new}$ in order to compute the
                    639: reduced Gr\"obner basis ${\cal G}_{new}$. This is possible due to the
                    640: binomial/monomial nature of all intermediate sets produced during the
                    641: algorithm. The weight vectors are carried implicitly in the markings
                    642: of these elements. This observation leads to considerable speed up of
                    643: the procedure.
                    644:
                    645: \begin{remark} \label{dianeobservation}
                    646: As in the proof of Algorithm~\ref{localchange}, let
                    647: $c_1 \in interior({\cal K})$ and $c_2 \in interior({\cal K}_{new})$.
                    648: Then notice that $in_{c_1}(I_A)$ is the initial ideal
                    649: of $W_{a_i - b_i} := \langle x^{a_i} - x^{b_i} \rangle + \langle
                    650: x^{a_j} \, : \, i \neq j, \, x^{a_j} \in in_{c_1}(I_A) \rangle$ with
                    651: respect to the marking $x^{a_i} > x^{b_i}$ while $in_{c_2}(I_A)$ is
                    652: the initial ideal of $W_{a_i - b_i}$ with respect to $x^{b_i} >
                    653: x^{a_i}$. See \cite{MT} for a generalization of this observation to
                    654: the theory of {\em $A$-graded ideals} (see Chapter 10 in \cite{Stu})
                    655: and the {\em toric Hilbert scheme}.
                    656: \end{remark}
                    657:
                    658: \begin{example}{\em For
                    659: $A := \left( \begin{array}{cccccc} 1 & 1 & 1 & 1 & 1 \\
                    660:                                    0 & 1 & 2 & 1 & 0 \\
                    661:                                    0 & 0 & 1 & 2 & 1 \end{array}
                    662: \right )$, consider the adjacent reduced Gr\"obner bases ${\cal G}_1$
                    663: and ${\cal G}_2$ that share the facet binomial $a^2d-be^2$.
                    664: The basis ${\cal G}_1  = \{ bd-ce, a^2d-be^2, b^2e-a^2c \}$ has facet
                    665: binomials $a^2d-be^2$ and $b^2e-a^2c$ and ${\cal G}_2 =
                    666: \{bd-ce, be^2-a^2d, a^2d^2-ce^3, b^2e-a^2c \}$ has facet binomials
                    667: $a^2d^2-ce^3$ and $be^2-a^2d$. We use Algorithm~\ref{localchange} to
                    668: compute ${\cal G}_2$ from ${\cal G}_1$.\\
                    669:
                    670: \noindent{\bf Step a.} $Old := \{ a^2d-be^2, bd, b^2e \}$.\\
                    671:
                    672: \noindent{\bf Step b.} $Temp := \{ be^2-a^2d, bd, b^2e \}$.\\
                    673:
                    674: \noindent{\bf Step c.} (i) $S$-pair$(be^2-a^2d,bd) = a^2d^2$.\\
                    675: $ Temp = \{ be^2-a^2d, bd, b^2e, a^2d^2 \}$.\\
                    676: (ii) $S$-pair$(be^2-a^2d, b^2e) = a^2bd \rightarrow 0$.\\
                    677: (iii) $S$-pair$(be^2-a^2d,a^2d^2) \rightarrow 0$.\\
                    678: Therefore $New = \{ be^2-a^2d, bd, b^2e, a^2d^2 \}$.\\
                    679:
                    680: \noindent{\bf Step d.} ${\cal G}' := \emptyset$.\\
                    681:
                    682: \noindent{\bf Step e.}
                    683: $be^2-a^2d = -1(a^2d-be^2)$. Therefore it lifts to $-1(full(a^2d-be^2))
                    684: = -1(a^2d-be^2) = be^2-a^2d$.\\
                    685: $bd = 1(bd)$. Therefore it lifts to $full(bd) = bd-ce$.\\
                    686: $b^2e = 1(b^2e)$. Therefore it lifts to $full(b^2e) = b^2e-a^2c$.\\
                    687: $a^2d^2 = d(a^2d-be^2) + e^2(bd)$.
                    688: Therefore it lifts to $d(full(a^2d-be^2)) + e^2(full(bd)) =
                    689: d(a^2d-be^2)+e^2(bd-ce) = a^2d^2 - bde^2 + bde^2 - ce^3 = a^2d^2 - ce^3$.\\
                    690: Hence ${\cal G}' = \{ be^2-a^2d, bd-ce, b^2e-a^2c, a^2d^2-ce^3\}$.\\
                    691:
                    692: \noindent{\bf Step f.} ${\cal G}_{new} =
                    693: \{ be^2-a^2d, bd-ce, b^2e-a^2c, a^2d^2-ce^3\}$.}
                    694: \end{example}
                    695: \subsection{Finding the facets of a toric Gr\"obner cone}
                    696:
                    697: For a general ideal, the Gr\"obner cone of one of its reduced
                    698: Gr\"obner bases is described by a large set of inequalities many of
                    699: which are redundant. Even for a toric ideal, empirical evidence
                    700: shows that the number of facet binomials of a reduced Gr\"obner basis may
                    701: be much smaller than the cardinality of the Gr\"obner basis. In fact,
                    702: it was conjectured in \cite{ST} that there is a function $\phi : {\bf
                    703: N} \rightarrow {\bf N}$ such that the number of facet binomials of a
                    704: reduced Gr\"obner basis of $I_A$ of codimension $k$ is bounded above
                    705: by $\phi(k)$. As a special case, it was conjectured in \cite{ST} that
                    706: $\phi(3) = 4$ based on empirical evidence with existing codes at the
                    707: time. Recently, Serkan Hosten and Diane Maclagan have found
                    708: counterexamples to this second conjecture using TiGERS. Lower bounds for
                    709: $\phi$ are given in \cite{ST}, although no good upper bound is known
                    710: for  the number of facets of a toric Gr\"obner cone. Hence,
                    711: identifying the facet binomials in a reduced Gr\"obner basis can
                    712: become a computationally expensive subroutine during the computation
                    713: of the Gr\"obner fan. In this section we discuss several ways to find
                    714: the facet binomials of a Gr\"obner cone in the case of a toric ideal.
                    715:
                    716: A first algorithm to compute the facets of a toric Gr\"obner cone
                    717: follows from Lemma~\ref{facets}. In practice this
                    718: can be an expensive procedure since we need to solve as many linear
                    719: programs as the cardinality of ${\cal G}$ and most binomials in ${\cal
                    720: G}$ are not facet binomials.
                    721:
                    722: \begin{algorithm} How to find the facet binomials of a reduced
                    723: Gr\"obner basis of $I_A$. \label{second}
                    724: \end{algorithm}
                    725: \noindent{\bf Input:} A reduced Gr\"obner basis ${\cal G} =
                    726: \{ {\underline x^{a_i}}-x^{b_i} :  i = 1,..,t \}$ of $I_A$.\\
                    727: \noindent{\bf Output:} The facet binomials of ${\cal G}$.\\
                    728: \indent Set Facets := $\emptyset$.\\
                    729: \indent For each binomial ${\underline x^{a_i}}-x^{b_i}$ in ${\cal G}$
                    730: do \\
                    731: \indent \indent If $a_i - b_i$ is not in the cone generated
                    732: by the vectors $\{a_j - b_j : {\underline x^{a_j}}-x^{b_j} \in {\cal
                    733: G}, i \neq j \}$\\
                    734: \indent \indent then Facets := Facets $\cup$ $\{x^{a_i}-x^{b_i}\}$.\\
                    735: \indent Output Facets.\\
                    736:
                    737: Algorithm~\ref{second} is dual to the algorithm suggested by
                    738: Lemma~\ref{facets} since $a_i \cdot u \geq b_i
                    739: \cdot u$ is a facet inequality of the Gr\"obner cone ${\cal K}$
                    740: of ${\cal G}$ if and only if $a_i - b_i$ is an extreme
                    741: ray (essential generator) of ${\cal K}^{\ast} := \{ v \in {\bf R}^n :
                    742: v \cdot u \geq 0, \, \forall u \in {\cal K}\}$ the polar cone of
                    743: ${\cal K}$. The vector $a_i - b_i$ is an extreme ray of ${\cal
                    744: K}^{\ast}$ if and only if
                    745: $a_i - b_i$ cannot be expressed as a non-negative linear combination
                    746: of the vectors $a_j - b_j$, $i \neq j$ where ${\underline
                    747: x^{a_j}}-x^{b_j} \in {\cal G}$. Algorithm~\ref{second} can be
                    748: implemented either by solving one linear program per binomial in
                    749: ${\cal G}$ or finding a generator representation of the cone ${\cal
                    750: K}^{\ast}$ using a convex hull package. We also obtain an easy
                    751: sufficient condition for a binomial in ${\cal G}$ to be a facet binomial.
                    752:
                    753: \begin{lemma}
                    754: Let ${\underline x^{a_i}}-x^{b_i}$ be an element of a reduced
                    755: Gr\"obner basis ${\cal G}$ of $I_A \subset k[x_1, \ldots, x_n]$ and
                    756: $x_k$ be a variable in $k[x_1, \ldots, x_n]$ such that $x_k$ divides
                    757: the leading term $x^{a_i}$ (respectively, the trailing term $x^{b_i}$)
                    758: of ${\underline x^{a_i}}-x^{b_i}$ but does not divide the leading terms
                    759: (respectively, trailing terms) of any other binomial in ${\cal G}$.
                    760: Then ${\underline x^{a_i}}-x^{b_i}$ is a facet binomial of ${\cal G}$.
                    761: \end{lemma}
                    762:
                    763: \noindent{\sl Proof:} If $k$ is in the support of $a_i$ (respectively
                    764: $b_i$) but not in the support of $a_j$ (respectively $b_j$) for $j
                    765: \neq i$, $j = 1,\ldots,t$, then $a_i - b_i$ cannot be a non-negative
                    766: linear combination of $a_j - b_j$ for $j \neq i$, $j =
                    767: 1,\ldots,t$. Hence $a_i - b_i$ is an extreme ray of the cone polar to
                    768: the Gr\"obner cone of ${\cal G}$.\\
                    769:
                    770: We now describe an algorithm to find a superset of the facet binomials
                    771: of a fixed reduced Gr\"obner basis of $I_A$ that does not require
                    772: linear programming. Our idea comes from results in \cite{MT}
                    773: (c.f. Remark~\ref{dianeobservation}).
                    774:
                    775: \begin{theorem} \cite{MT} \label{flippability}
                    776: Let ${\cal G}_c$ be the reduced Gr\"obner basis of
                    777: $I_A$ with respect to the generic weight vector $c \in {\bf R}^n$.
                    778: Then $x^a - x^b \in {\cal G}_c$ is a facet binomial of ${\cal G}_c$
                    779: only if $in_c(I_A)$ is the initial ideal of $W_{a-b} := \langle x^a -
                    780: x^b \rangle + \langle x^c \, : \, x^c \in in_c(I_A), \, x^c \neq x^a
                    781: \rangle$ with respect to $x^a > x^b$.
                    782: \end{theorem}
                    783:
                    784: The exact result in \cite{MT} is that if $x^a-x^b \in {\cal G}_c$
                    785: and $in_c(I_A)$ is the initial ideal of $W_{a-b}$ with respect to
                    786: $x^a > x^b$, then the initial
                    787: ideal $M$ of $W_{a-b}$ with respect to $x^b > x^a$ has the same
                    788: $A$-graded Hilbert function as $in_c(I_A)$. The latter is a necessary
                    789: condition for $M$ to be an initial ideal of $I_A$. For $M$ to be an
                    790: adjacent  initial ideal to $in_c(I_A)$, you need the additional
                    791: geometric requirement that $M$ and $in_c(I_A)$ share the facet given
                    792: by $x^a-x^b$. Hence the binomials in ${\cal G}_c$ that satisfy the
                    793: condition in Theorem~\ref{flippability} form a superset of the facet
                    794: binomials of ${\cal G}_c$. Once this superset has been found,
                    795: we use linear programming as before to identify the true facet binomials.
                    796:
                    797: \begin{algorithm}\label{third}
                    798: How to find a superset of the facet binomials of a reduced Gr\"obner
                    799: basis of $I_A$.
                    800: \end{algorithm}
                    801: \noindent {\bf Input:} A reduced Gr\"obner basis ${\cal G}_c$ of
                    802: $I_A$.\\
                    803: \noindent{\bf Output:} A superset $SS$ of the facet binomials of
                    804: ${\cal G}_c$.\\
                    805: \noindent Set $SS := \emptyset$\\
                    806: \indent For $x^a - x^b \in {\cal G}_c$ do \\
                    807: \indent \indent Let $W_{a-b} := \langle x^a - x^b \rangle + \langle
                    808: x^c \, : \, x^c \in in_c(I_A), \, x^c \neq x^a \rangle$.\\
                    809: \indent \indent If $in_c(I_A)$ is the initial ideal of $W_{a-b}$ with
                    810: respect to $x^a > x^b$ then $SS := SS$ union $\{x^a-x^b\}$.\\
                    811: Output $SS$.\\
                    812:
                    813: We remark that computing the reduced Gr\"obner basis and hence the
                    814: initial ideal of $W_{a-b}$ with respect to $x^a > x^b$ proceeds
                    815: exactly as in Algorithm~\ref{localchange} and is possible because of
                    816: the specific monomial/binomial structure of $W_{a-b}$. Surprisingly
                    817: it turns out that using Algorithm~\ref{third} can often result in
                    818: a $50\%$ speed up over using linear programming alone.
                    819: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                    820:
                    821: \section{Computational Experience}
                    822: The algorithms described in this paper have been implemented in {\tt C}
                    823: in a program called TiGERS which is available from the authors.
                    824: In this section we will describe some implementation issues,
                    825: optimizations and timings.
                    826: All timings in Table~\ref{TIMING} were obtained by running TiGERS on
                    827: a dual processor Pentium 450 with $1GB$ of RAM. With each example
                    828: problem, we list the following information about its state polytope:
                    829: $d$ its dimension, $f_0$ the number of vertices, $f_1$ the number of
                    830: edges, and $td$ the tree depth -- the longest chain in the reverse
                    831: search tree. We also list $mn$, the cardinality of the largest
                    832: Gr\"obner basis computed, $mf$, the largest number of facets in any
                    833: Gr\"obner basis, and $md$, the highest degree of a binomial
                    834: appearing in any of the Gr\"obner bases.
                    835: Timings are then given both for exhaustive search and reverse
                    836: search. Those in parentheses are timings using Algorithm~\ref{third}
                    837: to cut down on the number of linear programs needed to find facets.
                    838:
                    839: We first give a brief description of the examples in
                    840: Table~\ref{TIMING}. The first four examples are unrelated:
                    841: In {\tt pent} the matrix $A = \left( \begin{array}{ccccc}
                    842: 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1
                    843: \end{array} \right )$ the convex hull of whose columns is a pentagon
                    844: in the plane.
                    845: The matrix for ${\tt V23}$ is $A = \left( \begin{array}{cccccc}
                    846: 2 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 &
                    847: 2 \end{array} \right )$ whose toric variety is the second Veronese
                    848: embedding of ${\bf P}^2$, while $PV33$ refers to the {\em pinched
                    849: Veronese}\/ surface for which  $A = \left (
                    850: \begin{array}{ccccccccc} 3 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\
                    851: 0 & 1 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 3
                    852: \end{array} \right )$. The symbol {\tt gti} stands for the generic
                    853: toric ideal from Example 4.5 in \cite{PS} for which
                    854: $A = \left( \begin{array}{cccc} 20 & 24 & 25 & 31 \end{array} \right
                    855: )$. Examples $K5$ and $K6$ are specific instances of $Kn$, the
                    856: complete graph on $n$ vertices. The matrix associated to $Kn$ is the
                    857: node-edge incidence matrix of the graph (see Chapter 9 in \cite{Stu}).
                    858: The matrix $An := \left( 1 \,\,2\,\,3\,\,\ldots n \right )$ and the
                    859: Gr\"obner basis elements of the toric ideal $I_{An}$ correspond to
                    860: {\em primitive partition identities} with largest part $n$ (see Chapter 6 in
                    861: \cite{Stu} for details). The name $D r \times s$ refers to the $(r+s)
                    862: \times rs$ node-edge incidence matrix of an
                    863: undirected bipartite graph with $r$ nodes in one vertex class and $s$ nodes
                    864: in the other.
                    865:
                    866: The exhaustive search approach required a large amount of memory - in
                    867: the A9 example for instance, it was using about 600M by the end. In
                    868: addition to this, the amount of time needed to determine if a vertex
                    869: has been seen increases as the number of vertices found
                    870: increases. Even when memory size is not an issue we found that the
                    871: reverse search approach could end up by being faster than
                    872: the exhaustive search (see the A9 example).
                    873:
                    874: On the other hand, the reverse search implementation requires
                    875: us to traverse every edge and then check if it belonged to the reverse
                    876: search tree by finding the down edge for the new vertex.
                    877: If the edge used belongs to the reverse search tree, we keep the new vertex,
                    878: otherwise we discard it knowing that it has been seen before or will
                    879: be seen again. Thus instead of a large list search
                    880: we need only find the first mismarked facet binomial to decide whether
                    881: a vertex should be output. Furthermore, at each node we keep, we must
                    882: recompute its facet list every time we pass through it. By comparison
                    883: the exhaustive search algorithm required us to find facets only once per
                    884: vertex. One trick that we used to mitigate this
                    885: re-computation of facets was to save vertices and facet information
                    886: every time we went up in the tree,
                    887: so as to avoid recomputing the facets already visited. While this
                    888: approach means that we are no longer storing just one Gr\"obner basis, the
                    889: amount of storage required is still quite small, being bounded by the
                    890: tree depth.  In all the examples listed, the reverse search
                    891: (with caching) ran in under 750K.
                    892:
                    893: We conclude by drawing attention to the last entry in
                    894: Table~\ref{TIMING} denoted as {\tt HM} for which $A =
                    895: (247\,\,248\,\,345\,\,15)$. This was the original counter example found by
                    896: Hosten and Maclagan (c.f. page 10), using TiGERS, to the conjecture
                    897: that the maximum valency of a vertex in the state polytope of a corank
                    898: three matrix is four \cite{ST}.
                    899:
                    900: \begin{table}[hbt]
                    901: \begin{tabular}{||c||l|l|l|l||l|l|l||l|l||}\hline
                    902:                   Name & d & $f_0$ & $f_1$ &td & mn & mf & md & RS  & ES  \\
                    903: \hline\hline
                    904:   pent&  2&     8&      8& 4&  4&  2&  4&      0.00 & 0.00\\
                    905:   V23 &  3&    29&     45& 6&  7&  4&  3&      0.02 & 0.02(0.01)   \\
                    906:   gti &  3&   288&    467&30& 18&  4& 31& 2.30(1.27)& 1.50(0.76) \\
                    907:   PV33&  6& 54828& 190253&48& 36& 12&  7&  (4343.31)&  (3731.24)  \\
                    908: \hline
                    909:   K5  &  5 &     102 & 255 &14 & 11 & 5  & 3 & 0.36(0.32) & 0.28(0.24) \\
                    910:   K6  &  9 &  195720 &     &56 & 37 & 14 & 4 & 110111.68(50662.29)& \\
                    911: %  K7  & 14 &         &- &- & -   & -  & -  &  -        & -\\
                    912: \hline
                    913: %---------------------------------------------------------
                    914: %-- Familly related to primitive partition identities   --
                    915: %-- AN=[1,2,...,N] ---------------------------------------
                    916: %---------------------------------------------------------
                    917:    A4& 3 &     20&      31&  6&  8&  4& 4&     0.01(    0.01)&0.01(0.01) \\
                    918:    A5& 4 &    114&     249& 11& 14&  8& 5&     0.35(    0.28)&0.25(0.16)\\
                    919:    A6& 5 &    488&    1394& 18& 20& 12& 6&     6.78(    4.39)&4.33(2.37)\\
                    920:    A7& 6 &   4073&   14800& 28& 29& 18& 7&   239.80(  139.40)&159.96(82.01)\\
                    921:    A8& 7 &  25334&  111558& 41& 38& 24& 8&  5010.37( 2732.71)&3624(1867.85)\\
                    922:    A9& 8 & 206444& 1080981& 58& 49& 32& 9&127978.46(67565.22) & (71404.29) \\
                    923:   A10&  9 &$>$578435& -  & -  &  - & -  & - & -           & -      \\
                    924: \hline
                    925:
                    926: %---------------------------------------------------------
                    927: %-- DmxDn   2x2 minors of a mxn matrix -------------------
                    928: %---------------------------------------------------------
                    929:    D2x2& 3&  108&   222&  9& 10& 6& 3&  0.24( 0.20) &   0.23( 0.16) \\
                    930:    D2x3& 5& 4488& 14184& 19& 20& 8& 3&171.74(97.48) & 124.06(71.02) \\
                    931:    D3x3& 8&  $>$257057& & &    &   &   &              &  \\
                    932: \hline
                    933:  HM &3&904&1546&52 &40 &5&345&96.72(35.80)&76.08(21.53)\\
                    934: \hline
                    935: \end{tabular}
                    936: \caption{\label{TIMING} TiGERS Timings }
                    937: \end{table}
                    938: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                    939:
                    940: \begin{thebibliography}{9}
                    941:
                    942: \bibitem[AGK]{AGK} B. Amrhein, O. Gloor and W. K\"uchlin,
                    943: On the walk, {\em Theoretical Computer Science} {\bf 187}
                    944: (1997) 179--202.
                    945:
                    946: \bibitem[AF]{AF} D. Avis and K. Fukuda, A basis enumeration
                    947: algorithm for convex hulls and vertex enumeration of arrangements
                    948: and polyhedra, {\sl Discrete Computational Geometry} {\bf 8} (1992)
                    949: 295--313.
                    950:
                    951: \bibitem[AL]{AL} W.~W. Adams and P. Loustaunau,
                    952: {\sl An Introduction to Gr{\"o}bner Bases},
                    953: American Mathematical Society, 1994.
                    954:
                    955:
                    956: \bibitem[BM]{BM} D.~Bayer and I.~Morrison,
                    957: Standard bases and geometric invariant
                    958: theory I, {\sl Journal of Symbolic Computation} {\bf 6} (1988)
                    959: 209--217.
                    960:
                    961: \bibitem[BFS]{BFS}L.J.~Billera, P.~Filliman
                    962: and B.~Sturmfels, Constructions and complexity of
                    963: secondary polytopes, {\sl Advances in Mathematics} {\bf 83} (1990)
                    964: 155--179.
                    965:
                    966: \bibitem[CKM]{CKM} S.Collart, M.Kalkbrener and D.Mall, Converting
                    967: bases with the Gr\"obner walk, {\em Journal of Symbolic Computation}
                    968: {\bf 24} (1997) 465-469.
                    969:
                    970: \bibitem[GKZ]{GKZ} I.M.~Gel'fand, M.~Kapranov and A.~Zelevinsky,
                    971: {\sl Multidimensional Determinants, Discriminants and Resultants},
                    972:  Birkh\"auser, Boston, 1994.
                    973:
                    974: \bibitem[CLO]{CLO} D. Cox, J.  Little and D. O'Shea,
                    975: {\sl Ideals, Varieties, and Algorithms},
                    976: Springer-Verlag, New York, Second Edition, 1996.
                    977:
                    978: \bibitem[Mac]{Mac} D.~Maclagan, Antichains of monomial ideals are
                    979: finite, {\sl Manuscript}, 1998.
                    980:
                    981: \bibitem[MT]{MT} D.~Maclagan and R.~Thomas, On the combinatorics of
                    982: the toric Hilbert scheme, in preparation.
                    983:
                    984: \bibitem[MR]{MR} T.~Mora and L.~Robbiano,
                    985: The Gr\"obner fan of an ideal,
                    986: {\sl Journal of Symbolic Computation} {\bf 6} (1988) 183--208.
                    987:
                    988: \bibitem[PS]{PS} I.~Peeva and B.~Sturmfels,
                    989: Generic lattice ideals, Journal of the American Mathematical
                    990: Soceity {\bf 11} (1998) 363--373.
                    991:
                    992: \bibitem[Stu]{Stu} B.~Sturmfels, Gr\"obner bases and Convex Polytopes,
                    993: {\em American Mathematical Society}, Providence, RI, 1995.
                    994:
                    995: \bibitem[SST]{SST} M. Saito, B. Sturmfels and N. Takayama,
                    996: {\em Gr\"obner Deformations of Hypergeometric Differential Equations},
                    997: in preparation.
                    998:
                    999: \bibitem[ST]{ST} B.~Sturmfels and R.~Thomas, Variation
                   1000: of cost functions in integer programming, {\sl Mathematical Programming}
                   1001: {\bf 77} (1997) 357-387.
                   1002: \end{thebibliography}
                   1003:
                   1004: \end{document}
                   1005:
                   1006:
                   1007:
                   1008:
                   1009:
                   1010:
                   1011:
                   1012:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>