Annotation of OpenXM_contrib/TiGERS_0.9/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>
![[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