Annotation of OpenXM_contrib/TiGERS_0.9/paper/tiger.tex, Revision 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to tiger.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / TiGERS_0.9 / paper