COMPUTING GRÖBNER FANS OF TORIC IDEALS

BIRKETT HUBER AND REKHA R. THOMAS

Abstract. The monomial initial ideals of a graded polynomial ideal are in bijection with the vertices of a convex polytope known as the state polytope of the ideal. The Gröbner fan of the ideal is the normal fan of its state polytope. In this paper we present a software system called TiGERS for computing the Gröbner fan of a toric ideal by enumerating the edge graph of its state polytope. The key contributions are an inexpensive algorithm for local change of Gröbner bases in toric ideals and the identification of a reverse search tree on the vertices of the state polytope. Using these ideas we obtain a combinatorial Gröbner walk procedure for toric ideals. TiGERS has been used to compute state polytopes with over 200,000 vertices.

1. Introduction

Consider the polynomial ring k[x] := k[x_{1}, …, x_{n}] where k is a field and an ideal I ⊂ k[x] that is homogeneous with respect to a positive grading degree(x_{i}) = ω_{i} ∈ N\{0}. We use N to denote the set of non-negative integers. The initial ideal of I with respect to a term order ≻ on k[x] is the monomial ideal in_{≻}(I) := ⟨in_{≻}(f) : f ∈ I⟩ where in_{≻}(f) is the initial term of f ∈ I with respect to ≻. The reduced Gröbner basis of I with respect to ≻ is the unique finite set of monic polynomials G_{≻}(I) = {g_{1}, …, g_{t}} ⊂ I such that (i) in_{≻}(I) = ⟨in_{≻}(g_{1}), …, in_{≻}(g_{t})⟩ and (ii) for i ≠ j, no term of g_{i} is divisible by in_{≻}(g_{j}). Reduced Gröbner bases of polynomial ideals can be computed using Buchberger’s algorithm. See [AL] or [CLO] for further details.

Given an arbitrary weight vector c ∈ R^{n}, and a polynomial f = ∑ k_{α}x^{α} ∈ k[x], the initial term of f with respect to c is defined to be the sum of all terms k_{α}x^{α} in f such that the inner product c · α is maximal. The initial ideal of I with respect to c is then in_{c}(I) := ⟨in_{c}(f) : f ∈ I⟩. If in_{c}(I) is a monomial ideal then c is said to be generic for I. It is known that for a term order ≻ on k[x], there exists a weight vector c ∈ N^{n} such that in_{c}(I) = in_{≻}(I). In this case we say that c represents ≻ and it can be shown that in_{c}(I) = in_{≻}(I) if and only if in_{c}(g) = in_{≻}(g) for each g in G_{≻}(I).

Two weight vectors c_{1} and c_{2} in R^{n} are said to be equivalent modulo I whenever in_{c_{1}}(I) = in_{c_{2}}(I). The set of all weight vectors that are equivalent to c ∈ R^{n} form a relatively open polyhedral cone in R^{n}, the closure of which is called the Gröbner cone of c. The Gröbner cone of c is n-dimensional if and only if c is generic for I. The collection of all Gröbner cones of I form a polyhedral fan in R^{n} called the Gröbner fan of I [MR]. Since I is homogeneous with respect to a positive grading, this fan is, in fact, complete (i.e., covers R^{n}) and further, each Gröbner cone of I contains a strictly positive vector of R^{n}.

The Gröbner fan of I is the normal fan of a polytope in R^{n} called the state polytope of I [BM], denoted as St(I). Therefore, I has only finitely many distinct reduced Gröbner bases as c varies over all weight vectors in R^{n}. (See [Mac] for a new proof.) The faces of St(I) are in bijection with the distinct initial ideals of I, with the vertices of St(I) corresponding bijectively to the distinct monomial initial ideals of I. The distinct monomial initial ideals of I, in turn, are in bijection with the distinct reduced Gröbner bases of I obtained from term orders. Hence, computing all such initial ideals amounts to searching the edge graph of St(I). Two monomial initial ideals in_{c_{1}}(I) and in_{c_{2}}(I) are said to be adjacent if the corresponding vertices of St(I) are adjacent or equivalently, if the Gröbner cones of the generic weight vectors c_{1} and c_{2} share a common facet. See Chapters 1-3 in [Stu] for proofs of the results quoted above and a full discussion of Gröbner fans and state polytopes of graded polynomial ideals. Algorithms for their construction are also included.

Research at MSRI is supported in part by NSF grant DMS-9701755.

Given a matrix A = [a_{1}, …, a_{n}] ∈ Z^{d×n} of rank d, the toric ideal of A, denoted as I_{A}, is the kernel of the homomorphism k[x_{1}, …, x_{n}] → k[t_{1}^{±1}, …, t_{d}^{±1}], such that x_{j} ↦ t^{a_{j}} (see Chapter 4 in [Stu]). The ideal I_{A} is a d-dimensional prime ideal that is generated by the binomials x^{u^{+}} − x^{u^{−}} where u = u^{+} − u^{−} lies in the (n − d)-dimensional saturated lattice ker_{Z}(A) := {u ∈ Z^{n} : Au = 0}. Here u^{−} = (−u)^{+} and u^{+} is defined as u_{i}^{+} = u_{i} if u_{i} > 0 and u_{i}^{+} = 0 otherwise. Hence u^{+}, u^{−} ∈ N^{n}. The mechanics of the Buchberger algorithm ensure that every reduced Gröbner basis of I_{A} again consists of finitely many binomials of the above type. We will assume that ker_{Z}(A) ∩ N^{n} = {0} which guarantees a positive integral vector ω in the row space of A. Then I_{A} is homogeneous with respect to the grading degree(x_{i}) = ω_{i}.

Let G_{c} = {x^{α_{i}} − x^{β_{i}} : i = 1, …, t} be the reduced Gröbner basis of I_{A} with respect to a generic weight vector c ∈ R^{n}. (The positive term of a binomial in G_{c} is always assumed to be the initial term with respect to c.) The Gröbner cone of c is then the n-dimensional polyhedral cone K_{c} := {u ∈ R^{n} : α_{i}·u ≥ β_{i}·u, i = 1, …, t} whose lineality space (K_{c}∩−K_{c}) is the row space of A. We may assume that c is a strictly positive integral vector since K_{c} is a rational cone and ω ∈ K_{c}. Further, c′ is equivalent to c if and only if in_{c′}(x^{α_{i}} − x^{β_{i}}) = x^{α_{i}} for each binomial x^{α_{i}} − x^{β_{i}} ∈ G_{c}. State polytopes and Gröbner fans of toric ideals were studied in [ST]. This paper gives several custom-tailored construction methods for these entities when the ideal is toric.

The Gröbner fan of I_{A} has various applications: In [ST] it was used as a model for sensitivity analysis for the family of integer programs min{c · x : Ax = b, x ∈ N^{n}} as b varies in Z^{d} and c in R^{n}. The secondary fan of A [BFS], [GKZ] is a coarsening of the Gröbner fan of I_{A} (see Chapter 8 in [Stu]). This fan has important applications to problems in discrete geometry. In between the secondary fan and the Gröbner fan of A lives the hypergeometric fan of A which has been used for studying A-hypergeometric differential equations using Gröbner deformations [SST]. Both these coarser fans can be obtained from the Gröbner fan of I_{A}. Finally, the Gröbner walk procedure introduced in [CKM] uses the Gröbner fan for Gröbner basis conversions.

Example 1.0.1. Let A := ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1 \end{matrix} ). For ease of exposition we associate the

variables a, b, c, d, e to the five columns of A and consider the toric ideal I_{A} ⊂ k[a, b, c, d, e]. This ideal yields eight distinct monomial initial ideals. The state polytope St(I_{A}) is an octagon in R^{5} and the Gröbner fan of I_{A} can be drawn in R^{2} after moding out the row space of A from each Gröbner cone. Figure 1 shows a schematic representation of the resulting pointed Gröbner fan of I_{A}. Each maximal cone is labeled by the reduced Gröbner basis induced by the weight vectors in the interior of that cone. The binomials in a reduced Gröbner basis that contribute the facet inequalities of its Gröbner cone are marked with dots. Notice that for two adjacent reduced Gröbner bases, their common facet binomial x^{α} − x^{β} appears in both reduced Gröbner bases with x^{α} as initial term in one basis and x^{β} as initial term in the other.

[figure: \begin{aligned}• & a^{2}c − b^{2}e \\ & a^{2}d − be^{2} \\ • & bd − ce \end{aligned}; \begin{aligned}• & b^{2}e − a^{2}c \\ • & a^{2}d − be^{2} \\ & bd − ce \end{aligned}; \begin{aligned}• & a^{2}d^{2} − ce^{3} \\ & b^{2}e − a^{2}c \\ • & be^{2} − a^{2}d \\ & bd − ce \end{aligned}; \begin{aligned}• & ce^{3} − a^{2}d^{2} \\ & b^{2}e − a^{2}c \\ & be^{2} − a^{2}d \\ • & bd − ce \end{aligned}; \begin{aligned}• & b^{3}d − a^{2}c^{2} \\ & b^{2}e − a^{2}c \\ & be^{2} − a^{2}d \\ • & ce − bd \end{aligned}; \begin{aligned}• & a^{2}c^{2} − b^{3}d \\ • & b^{2}e − a^{2}c \\ & be^{2} − a^{2}d \\ & ce − bd \end{aligned}; \begin{aligned}• & a^{2}c − b^{2}e \\ • & be^{2} − a^{2}d \\ & ce − bd \end{aligned}; \begin{aligned}& a^{2}c − b^{2}e \\ • & a^{2}d − be^{2} \\ • & ce − bd \end{aligned}]

Figure 1. A schematic of the Gröbner fan in Example 1.0.1

In this paper we introduce a software system called TiGERS for computing the Gröbner fan of a toric ideal. The program searches the edge graph of the state polytope St(I_{A}) to find all the distinct monomial initial ideals (reduced Gröbner bases) of I_{A}. This search can be done in two ways: For moderate sized examples, the graph is searched by a breadth-first search strategy on the entire edge-graph of St(I_{A}). This approach needs to maintain and search the list of all Gröbner bases found. When St(I_{A}) is too large this approach will bog down and we use a reverse search technique instead. This involves a depth-first search on a subgraph of the edge graph of St(I_{A}) called the reverse search tree, and can be implemented so that no more than one Gröbner basis ever needs to be stored. In Section 2 we give an overview of the main algorithm in TiGERS and describe the reverse search procedure. These ideas allow combinatorial Gröbner walks in toric ideals. For each reduced Gröbner basis found, the algorithm does two main local computations. The first is to determine all the facets of that Gröbner cone and the second is to determine an adjacent Gröbner basis to the current one. In Section 3 we give an algorithm for local change of Gröbner bases in toric ideals based on [CKM]. Unlike usual local change algorithms, our procedure does not require any weight vectors to be computed. We then discuss some special tricks to find the facets of a fixed Gröbner cone in the case of toric ideals. Section 4 reports computational experience with TiGERS.

2. The main algorithm in TiGERS

Let G_{c} = {x^{α_{i}} − x^{β_{i}}, i = 1, …, t} be the reduced Gröbner basis of I_{A} with respect to the generic weight vector c ∈ R^{n}. An inequality α_{k} · u ≥ β_{k} · u, k ∈ {1, …, t} is irredundant for the Gröbner cone K_{c} = {u ∈ R^{n} : α_{i} · u ≥ β_{i} · u, i = 1, …, t} if the relaxed cone {u ∈ R^{n} : α_{i} · u ≥ β_{i} · u, i = 1, …, t, i ≠ k} properly contains K_{c}. If α_{k} · u ≥ β_{k} · u is irredundant for K_{c} then K_{c} ∩ {u ∈ R^{n} : α_{k} · u = β_{k} · u} is called a facet of K_{c} and x^{α_{k}} − x^{β_{k}} is a facet binomial of G_{c}.

Lemma 2.0.2. [ST] The binomial x^{α_{k}} − x^{β_{k}} ∈ G_{c} is a facet binomial of G_{c} if and only if the linear system {u ∈ R^{n} : α_{i} · u ≥ β_{i} · u , i = 1, …, t, i ≠ k} ∪ {u ∈ R^{n} : β_{k} · u ≥ α_{k} · u} is feasible.

Therefore, all facets of the Gröbner cone K_{c} can be found by checking the feasibility of t systems of linear inequalities, which in turn can be done by linear programming. In practice this can be computationally expensive when t is large and we discuss certain speed ups in Section 3.2.

Suppose x^{α} −x^{β} is a facet binomial of G_{c} such that in_{c}(x^{α} −x^{β}) = x^{α} and G_{c′} be adjacent to G_{c} with in_{c′}(x^{α} − x^{β}) = x^{β}. In order to compute the edge graph of St(I_{A}), we require a subroutine to make a local change of reduced Gröbner bases from G_{c} to G_{c′} through the facet given by x^{α} − x^{β}. We use flip(G_{c}, x^{α} − x^{β}) to denote both the subroutine that yields G_{c′} from G_{c} as well as the reduced Gröbner basis G_{c′} that results from the “flip”. In Section 3.1 we describe the precise local change algorithm in TiGERS.

Remark 2.0.3. If x^{α} − x^{β} lies in the reduced Gröbner basis of a toric ideal, then the supports of α and β are disjoint. This guarantees that each facet in a toric Gröbner cone corresponds to precisely one binomial in the corresponding Gröbner basis. However, this is not true for general homogeneous binomial ideals. Consider J = ⟨b^{3}d−b^{2}ce, a2c−b2e, bcd− c2e⟩. Under the reverse lexicographic order a ≻ c ≻ d ≻ e ≻ b, its reduced Gröbner basis is G = {ceb^{2} − db^{3}, c^{2}e − cdb, a^{2}db^{3} − e^{2}b^{4}, a^{2}c − eb^{2}}. The inequality u_{3} + u_{5} ≥ u_{2} + u_{4} is a facet inequality of the Gröbner cone of G. For ω in the relative interior of this facet, we get both in_{ω}(ceb^{2} − db^{3}) = ceb^{2} − db^{3} and in_{ω}(c^{2}e − cdb) = c^{2}e − cdb.

Algorithm 2.0.4. Enumerating the edge graph of St(I_{A}) via breadth-first search.

Input: Any reduced Gröbner basis G_{0} of I_{A}. Output: All reduced Gröbner bases of I_{A} (all vertices of St(I_{A})).

Todo := [G_{0}];

  Verts := [ ];

While(Todo not empty) do G := first-element-in(Todo); Remove G from Todo; add G to Verts; determine list L of facet binomials of G for each x^{α} − x^{β} in L do

Compute G′ = flip(G, x^{α} − x^{β})

If G′ ∉ Todo ∪ Verts then add G′ to Todo; End

End

output Verts

This algorithm works well in practice but does have the drawback that all vertices must be stored, and that every time a vertex is visited it must be checked against all other vertices seen thus far in order to determine if it is indeed a new vertex. The storage and search costs involved in this procedure can become prohibitive as the size of St(I_{A}) increases. As an

example consider A := ( \begin{matrix}3 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 3 \end{matrix} ). The ideal I_{A} involves only nine

variables and most reduced Gröbner bases of this ideal have fewer than 36 elements each of degree no greater than seven. Yet, St(I_{A}) has 54, 828 vertices and our breadth first search algorithm was exhausting a personal computer with 64 kilobytes of memory before getting through about 13, 000 vertices. In order to push this calculation through we resorted to the reverse enumeration paradigm of Avis and Fukuda [AF]. The basic idea there is to do a depth first search on a directed subgraph of St(I_{A}).

We say that a polynomial f ∈ k[x] is marked by a term order ≻ on k[x], if the initial term of f with respect to ≻ has been distinguished from among all terms in f. A polynomial f that has been marked with respect to ≻ is said to be mismarked with respect to ≻′, if in_{≻}(f) ≠ in_{≻′}(f).

Lemma 2.0.5. Let G_{≻} be the reduced Gröbner basis of I_{A} with respect to the term order ≻. Then for a term order ≻′≠≻, the reduced Gröbner basis G_{≻′} equals G_{≻} if and only if no facet binomial of G_{≻} is mismarked with respect to ≻′.

Proof: Suppose no facet binomial of G_{≻} is mismarked with respect to ≻′ and let c′ be a weight vector from the interior of the Gröbner cone K_{≻′}. Then for each facet binomial x^{α} − x^{β} in G_{≻}, we have c′ · α > c′ · β which implies that c′ lies in the interior of the Gröbner cone K_{≻}. Hence K_{≻′} = K_{≻} which implies that G_{≻} = G_{≻′}. Conversely, if G_{≻} = G_{≻′}, then no binomial in G_{≻} is mismarked with respect to ≻′.

Definition 2.0.6. For a given term order ≻ we define the reverse search tree T_{≻}(I_{A}) as follows: The vertices of T_{≻}(I_{A}) are the vertices of St(I_{A}) (i.e. the various reduced Gröbner bases of I_{A} arising from term orders). For two reduced Gröbner bases G_{i} and G_{j}, [G_{i}, G_{j}] directed from G_{i} to G_{j} is an edge of T_{≻}(I_{A}) if G_{j} is obtained from G_{i} by the subroutine flip(G_{i}, x^{α}−x^{β}) where x^{α} − x^{β} is the unique facet binomial of G_{i} whose leading term is lexicographically maximal among all facet binomials of G_{i} that are mismarked with respect to ≻.

Theorem 2.0.7. The reverse search tree T_{≻}(I_{A}) is an acyclic directed graph with a unique sink.

Proof: By Lemma 2.0.5 each reduced Gröbner basis G of I_{A} (vertex of St(I_{A})) except G_{≻} has at least one mismarked facet binomial with respect to ≻. By the definition of T_{≻}(I_{A}), each such G has a unique adjacent reduced Gröbner basis given by flip(G, x^{α} − x^{β}) where x^{α} − x^{β} is the unique facet binomial of G whose leading term is lexicographically maximal among all mismarked facet binomials of G. Therefore T_{≻}(I_{A}) is a directed graph such that the out-degree of G_{≻} in T_{≻}(I_{A}) is zero and of all other reduced Gröbner bases is one.

Suppose there was a cycle C = (v_{1}, …, v_{l}) of length l in T_{≻}(I_{A}) where vertex v_{i} corresponds to the reduced Gröbner basis G_{i} of I_{A} and v_{l+1} = v_{1} and G_{l+1} = G_{1}. If x^{α_{i}} − x^{β_{i}} is the common facet binomial of G_{i} and G_{i+1} with x^{α_{i}} the leading term with respect to G_{i} and x^{β_{i}} the leading term with respect to G_{i+1} for i = 1, …, l, then v_{i+1} − v_{i} = β_{i} − α_{i} for i = 1, …, l. Since C is a cycle in T_{≻}(I_{A}) we get (β_{1} − α_{1}) + (β_{2} − α_{2}) + ⋯ + (β_{l} − α_{l}) = 0. However, each binomial x^{α_{i}} − x^{β_{i}} for i = 1, …, l is mismarked with respect to ≻ which implies that for a weight vector c representing ≻ we have, c · (β_{i} − α_{i}) > 0. This leads to the contradiction 0 = c · ∑_{i=1}^{l}(β_{i} − α_{i}) = ∑_{i=1}^{l} c · (β_{i} − α_{i}) > 0.

Corollary 2.0.8. From any reduced Gröbner basis G_{c} of I_{A} there is a unique path in the reverse search tree T_{≻}(I_{A}) to the sink G_{≻}.

Corollary 2.0.8 proves that toric ideals admit combinatorial Gröbner walks that can be used for converting one reduced Gröbner basis of I_{A} into another. Given any reduced Gröbner basis G of I_{A} and any term order ≻, we can move from G to G_{≻} by tracing the unique path in the reverse search tree T_{≻}(I_{A}) from G to G_{≻}. Unlike in the usual Gröbner walk procedure [CKM],[AGK] to convert one Gröbner basis into another there are no explicit cost vectors involved in these walks. These combinatorial walks also have the advantage that there is never the danger of walking through a lower dimensional face of a Gröbner cone thus eliminating several numerical considerations that otherwise have to be dealt with. The trade off is that at every vertex of the state polytope, all facets of the current Gröbner cone have to be computed which can be highly non-trivial for general ideals, but is relatively easy for toric ideals.

Algorithm 2.0.9. Enumerating the edge graph of St(I_{A}) via reverse search. Input: A reduced Gröbner basis R_{≻} of I_{A} and its term order ≻. Output: All reduced Gröbner bases of I_{A} (all vertices of St(I_{A})).

set G := R_{≻}; j:=0 ; L := list of facet binomials of G which are marked by ≻ output G repeat

while j < |L| do j := j + 1. G′ := flip(G, L[j]); if [G′,G] in T_{≻}(I_{A}) then

G:= G′; j := 0; L := list of facets of G marked by ≻ output G

endif endwhile If G ≠ R_{≻} then

G′ := unique element such that [G,G′] in T_{≻}(I_{A}); j := 0; L := list of facets of G′ marked by ≻ repeat j := j + 1 until the common facet of G and G′ is the jth facet of L. G := G′

endif until G = R_{≻} and j = |L|.

3. Local Computations

Having given an overview of the algorithm in TiGERS for computing the Gröbner fan of a toric ideal, we now focus on the computations that have to be made at a fixed reduced Gröbner basis encountered while searching the edge graph of St(I_{A}). The two main issues here are (i) how to compute a Gröbner basis that shares a prescribed facet binomial with the current basis and (ii) how to compute all the facets of a toric Gröbner cone.

3.1. Local change of Gröbner bases in toric ideals.

Algorithm 3.1.1. Local change of reduced Gröbner bases in I_{A}. (a specialization of [CKM] and Subroutine 3.7 in [Stu]).

Input: (i) A reduced Gröbner basis G = \{\underline{x}^{a_{k}} − x^{b_{k}} : k = 1, .., t\} of I_{A}. (The weight vector inducing G is generic and the underlined terms are the leading terms.) (ii) A prescribed facet binomial \underline{x}^{a_{i}} − x^{b_{i}} of G. Output: The reduced Gröbner basis adjacent to G in which \underline{x}^{b_{i}} − x^{a_{i}} is a facet binomial.

a. Let Old := \{\underline{x}^{a_{i}} − x^{b_{i}}\} ∪ \{\underline{x}^{a_{j}} : \underline{x}^{a_{j}} − x^{b_{j}} ∈ G, j ≠ i\}.

b. Let T emp be got from Old by switching the marking on the binomial in Old.

i.e., T emp := \{\underline{x}^{b_{i}} − x^{a_{i}}\} ∪ \{\underline{x}^{a_{j}} : x^{a_{j}} ∈ Old\}. c. Compute the reduced Gröbner basis of T emp with respect to the new marking.

Store the (marked) result in New. d. Set G′ := ∅ e. For each h in New DO

(i) Reduce h to zero modulo Old keeping track of the coefficients during reduction. This gives the representation

h = ∑_{g∈Old} p_{g} · g

(ii) Compute the polynomial

∑_{full(g)∈G} p_{g} · full(g)

and add it to the set G′. (full(g) ∈ G is the completion of g ∈ Old.) f. Auto-reduce G′ with respect to the markings in New to get G_{new}.

Then G_{new} is the reduced Gröbner basis adjacent to G such that \underline{x}^{a_{i}} −x^{b_{i}} is a facet binomial in G and \underline{x}^{b_{i}} − x^{a_{i}} is a facet binomial in G_{new}.

Proof of correctness: Let K and K_{new} be the Gröbner cones of G and G_{new} respectively. The linear span of the common facet of K and K_{new} is {u ∈ R^{n} : a_{i} · u = b_{i} · u}. Let c_{1} ∈ interior(K), c_{2} ∈ interior(K_{new}) and c be a vector in the relative interior of K ∩K_{new}. By definition, Old = in_{c}(G) := {in_{c}(f) : f ∈ G} and with respect to the markings specified in Step a, Old is the reduced Gröbner basis of in_{c}(I_{A}) with respect to c_{1}. Since T emp is got from Old by simply reversing the marking on the facet binomial x^{a_{i}} − x^{b_{i}}, T emp is a generating set for in_{c}(I_{A}).

We first show that the set New computed in Step c, using T emp as input, is the reduced Gröbner basis of in_{c}(I_{A}) with respect to c_{2}. Clearly the marked monomials in T emp are their own initial terms with respect to c_{2}. The non-trivial S-pair computations in Step c are those between a monomial x^{a_{j}}, j ≠ i, and the binomial \underline{x}^{b_{i}} − x^{a_{i}}. This results in a monomial which either reduces to zero with respect to the current partial Gröbner basis or reduces to a monomial that gets added to the current partial Gröbner basis. There is no point during this process at which an unmarked binomial is produced that is required to be marked. No binomials are produced during such an S-pair reduction either. Hence all subsequent S-pair computations are also of the above nature and so in fact, the set New is as claimed above and consists of the binomial \underline{x}^{b_{i}} − x^{a_{i}} along with monomials some of which were possibly produced during the Buchberger process. Steps d and e simply lift New to a minimal Gröbner basis G′ of I_{A} with respect to c_{2}. Finally, Step f auto-reduces this minimal Gröbner basis to the reduced Gröbner basis G_{new} of I_{A} with respect to c_{2}.

The most important computational advantage of the above local change algorithm is that it does not require the computation of a weight vector in the interior of K_{new} in order to compute the reduced Gröbner basis G_{new}. This is possible due to the binomial/monomial nature of all intermediate sets produced during the algorithm. The weight vectors are carried implicitly in the markings of these elements. This observation leads to considerable speed up of the procedure.

Remark 3.1.2. As in the proof of Algorithm 3.1.1, let c_{1} ∈ interior(K) and c_{2} ∈ interior(K_{new}). Then notice that in_{c_{1}}(I_{A}) is the initial ideal of W_{a_{i}−b_{i}} := ⟨x^{a_{i}} − x^{b_{i}}⟩ + ⟨x^{a_{j}} : i ≠ j, x^{a_{j}} ∈ in_{c_{1}}(I_{A})⟩ with respect to the marking x^{a_{i}} > x^{b_{i}} while in_{c_{2}}(I_{A}) is the initial ideal of W_{a_{i}−b_{i}} with respect to x^{b_{i}} > x^{a_{i}}. See [MT] for a generalization of this observation to the theory of A-graded ideals (see Chapter 10 in [Stu]) and the toric Hilbert scheme.

Example 3.1.3. For A := ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1 \end{matrix} ), consider the adjacent reduced Gröbner

bases G_{1} and G_{2} that share the facet binomial a^{2}d − be^{2}. The basis G_{1} = {bd − ce, a^{2}d − be^{2}, b^{2}e−a^{2}c} has facet binomials a^{2}d−be^{2} and b^{2}e−a^{2}c and G_{2} = {bd−ce, be^{2}−a^{2}d, a^{2}d^{2}− ce^{3}, b^{2}e − a^{2}c} has facet binomials a^{2}d^{2} − ce^{3} and be^{2} − a^{2}d. We use Algorithm 3.1.1 to compute G_{2} from G_{1}.

Step a. Old := {a^{2}d − be^{2}, bd, b^{2}e}.

Step b. T emp := {be^{2} − a^{2}d, bd, b^{2}e}.

Step c. (i) S-pair(be^{2} − a^{2}d, bd) = a^{2}d^{2}. T emp = {be^{2} − a^{2}d, bd, b^{2}e, a^{2}d^{2}}. (ii) S-pair(be^{2} − a^{2}d, b^{2}e) = a^{2}bd → 0. (iii) S-pair(be^{2} − a^{2}d, a^{2}d^{2}) → 0. Therefore New = {be^{2} − a^{2}d, bd, b^{2}e, a^{2}d^{2}}.

Step d. G′ := ∅.

Step e. be^{2} − a^{2}d = −1(a^{2}d − be^{2}). Therefore it lifts to −1(full(a^{2}d − be^{2})) = −1(a^{2}d − be^{2}) = be^{2} − a^{2}d. bd = 1(bd). Therefore it lifts to full(bd) = bd − ce. b^{2}e = 1(b^{2}e). Therefore it lifts to full(b^{2}e) = b^{2}e − a^{2}c. a^{2}d^{2} = d(a^{2}d − be^{2}) + e^{2}(bd). Therefore it lifts to d(full(a^{2}d − be^{2})) + e^{2}(full(bd)) = d(a^{2}d − be^{2}) + e^{2}(bd − ce) = a^{2}d^{2} − bde^{2} + bde^{2} − ce^{3} = a^{2}d^{2} − ce^{3}. Hence G′ = {be^{2} − a^{2}d, bd − ce, b^{2}e − a^{2}c, a^{2}d^{2} − ce^{3}}.

Step f. G_{new} = {be^{2} − a^{2}d, bd − ce, b^{2}e − a^{2}c, a^{2}d^{2} − ce^{3}}.

3.2. Finding the facets of a toric Gröbner cone. For a general ideal, the Gröbner cone of one of its reduced Gröbner bases is described by a large set of inequalities many of which are redundant. Even for a toric ideal, empirical evidence shows that the number of facet binomials of a reduced Gröbner basis may be much smaller than the cardinality of the Gröbner basis. In fact, it was conjectured in [ST] that there is a function ϕ : N → N such that the number of facet binomials of a reduced Gröbner basis of I_{A} of codimension k is bounded above by ϕ(k). As a special case, it was conjectured in [ST] that ϕ(3) = 4 based on empirical evidence with existing codes at the time. Recently, Serkan Hosten and Diane Maclagan have found counterexamples to this second conjecture using TiGERS. Lower bounds for ϕ are given in [ST], although no good upper bound is known for the number of facets of a toric Gröbner cone. Hence, identifying the facet binomials in a reduced Gröbner basis can become a computationally expensive subroutine during the computation of the Gröbner fan. In this section we discuss several ways to find the facet binomials of a Gröbner cone in the case of a toric ideal.

A first algorithm to compute the facets of a toric Gröbner cone follows from Lemma 2.0.2. In practice this can be an expensive procedure since we need to solve as many linear programs as the cardinality of G and most binomials in G are not facet binomials.

Algorithm 3.2.1. How to find the facet binomials of a reduced Gröbner basis of I_{A}.

Input: A reduced Gröbner basis G = \{\underline{x}^{a_{i}} − x^{b_{i}} : i = 1, .., t\} of I_{A}. Output: The facet binomials of G.

Set Facets := ∅.

For each binomial \underline{x}^{a_{i}} − x^{b_{i}} in G do If a_{i} − b_{i} is not in the cone generated by the vectors \{a_{j} − b_{j} : \underline{x}^{a_{j}} − x^{b_{j}} ∈ G, i ≠ j\} then Facets := Facets ∪ {x^{a_{i}} − x^{b_{i}}}.

Output Facets.

Algorithm 3.2.1 is dual to the algorithm suggested by Lemma 2.0.2 since a_{i} · u ≥ b_{i} · u is a facet inequality of the Gröbner cone K of G if and only if a_{i} − b_{i} is an extreme ray (essential generator) of K^{∗} := {v ∈ R^{n} : v · u ≥ 0, ∀u ∈ K} the polar cone of K. The vector a_{i} − b_{i} is an extreme ray of K^{∗} if and only if a_{i} − b_{i} cannot be expressed as a non-negative linear combination of the vectors a_{j} − b_{j}, i ≠ j where \underline{x}^{a_{j}} − x^{b_{j}} ∈ G. Algorithm 3.2.1 can be implemented either by solving one linear program per binomial in G or finding a generator representation of the cone K^{∗} using a convex hull package. We also obtain an easy sufficient condition for a binomial in G to be a facet binomial.

Lemma 3.2.2. Let \underline{x}^{a_{i}}−x^{b_{i}} be an element of a reduced Gröbner basis G of I_{A} ⊂ k[x_{1}, …, x_{n}] and x_{k} be a variable in k[x_{1}, …, x_{n}] such that x_{k} divides the leading term x^{a_{i}} (respectively, the trailing term x^{b_{i}}) of \underline{x}^{a_{i}} −x^{b_{i}} but does not divide the leading terms (respectively, trailing terms) of any other binomial in G. Then \underline{x}^{a_{i}} − x^{b_{i}} is a facet binomial of G.

Proof: If k is in the support of a_{i} (respectively b_{i}) but not in the support of a_{j} (respectively b_{j}) for j ≠ i, j = 1, …, t, then a_{i} − b_{i} cannot be a non-negative linear combination of a_{j} − b_{j} for j ≠ i, j = 1, …, t. Hence a_{i} − b_{i} is an extreme ray of the cone polar to the Gröbner cone of G.

We now describe an algorithm to find a superset of the facet binomials of a fixed reduced Gröbner basis of I_{A} that does not require linear programming. Our idea comes from results in [MT] (c.f. Remark 3.1.2).

Theorem 3.2.3. [MT] Let G_{c} be the reduced Gröbner basis of I_{A} with respect to the generic weight vector c ∈ R^{n}. Then x^{a} − x^{b} ∈ G_{c} is a facet binomial of G_{c} only if in_{c}(I_{A}) is the initial ideal of W_{a−b} := ⟨x^{a} − x^{b}⟩ + ⟨x^{c} : x^{c} ∈ in_{c}(I_{A}), x^{c} ≠ x^{a}⟩ with respect to x^{a} > x^{b}.

The exact result in [MT] is that if x^{a} − x^{b} ∈ G_{c} and in_{c}(I_{A}) is the initial ideal of W_{a−b} with respect to x^{a} > x^{b}, then the initial ideal M of W_{a−b} with respect to x^{b} > x^{a} has the same A-graded Hilbert function as in_{c}(I_{A}). The latter is a necessary condition for M to be an initial ideal of I_{A}. For M to be an adjacent initial ideal to in_{c}(I_{A}), you need the additional geometric requirement that M and in_{c}(I_{A}) share the facet given by x^{a} − x^{b}.

Hence the binomials in G_{c} that satisfy the condition in Theorem 3.2.3 form a superset of the facet binomials of G_{c}. Once this superset has been found, we use linear programming as before to identify the true facet binomials.

Algorithm 3.2.4. How to find a superset of the facet binomials of a reduced Gröbner basis of I_{A}.

Input: A reduced Gröbner basis G_{c} of I_{A}. Output: A superset SS of the facet binomials of G_{c}. Set SS := ∅

For x^{a} − x^{b} ∈ G_{c} do Let W_{a−b} := ⟨x^{a} − x^{b}⟩ + ⟨x^{c} : x^{c} ∈ in_{c}(I_{A}), x^{c} ≠ x^{a}⟩. If in_{c}(I_{A}) is the initial ideal of W_{a−b} with respect to x^{a} > x^{b} then SS := SS union

{x^{a} − x^{b}}. Output SS.

We remark that computing the reduced Gröbner basis and hence the initial ideal of W_{a−b} with respect to x^{a} > x^{b} proceeds exactly as in Algorithm 3.1.1 and is possible because of the specific monomial/binomial structure of W_{a−b}. Surprisingly it turns out that using Algorithm 3.2.4 can often result in a 50% speed up over using linear programming alone.

4. Computational Experience

The algorithms described in this paper have been implemented in C in a program called TiGERS which is available from the authors. In this section we will describe some implementation issues, optimizations and timings. All timings in Table 1 were obtained by running TiGERS on a dual processor Pentium 450 with 1GB of RAM. With each example problem, we list the following information about its state polytope: d its dimension, f_{0} the number of vertices, f_{1} the number of edges, and td the tree depth – the longest chain in the reverse search tree. We also list mn, the cardinality of the largest Gröbner basis computed, mf, the largest number of facets in any Gröbner basis, and md, the highest degree of a binomial appearing in any of the Gröbner bases. Timings are then given both for exhaustive search and reverse search. Those in parentheses are timings using Algorithm 3.2.4 to cut down on the number of linear programs needed to find facets.

We first give a brief description of the examples in Table 1. The first four examples are

unrelated: In pent the matrix A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1 \end{matrix} ) the convex hull of whose columns

is a pentagon in the plane. The matrix for V23 is A = ( \begin{matrix}2 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{matrix} ) whose

toric variety is the second Veronese embedding of P^{2}, while P V 33 refers to the pinched

Veronese surface for which A = ( \begin{matrix}3 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 3 \end{matrix} ). The symbol gti stands

for the generic toric ideal from Example 4.5 in [PS] for which A = ( 20 24 25 31 ). Examples K5 and K6 are specific instances of Kn, the complete graph on n vertices. The matrix associated to Kn is the node-edge incidence matrix of the graph (see Chapter 9 in [Stu]). The matrix An := (1 2 3 … n) and the Gröbner basis elements of the toric ideal I_{An} correspond to primitive partition identities with largest part n (see Chapter 6 in [Stu] for details). The name Dr × s refers to the (r + s) × rs node-edge incidence matrix of an undirected bipartite graph with r nodes in one vertex class and s nodes in the other.

The exhaustive search approach required a large amount of memory - in the A9 example for instance, it was using about 600M by the end. In addition to this, the amount of time needed to determine if a vertex has been seen increases as the number of vertices found increases. Even when memory size is not an issue we found that the reverse search approach could end up by being faster than the exhaustive search (see the A9 example).

On the other hand, the reverse search implementation requires us to traverse every edge and then check if it belonged to the reverse search tree by finding the down edge for the new vertex. If the edge used belongs to the reverse search tree, we keep the new vertex, otherwise we discard it knowing that it has been seen before or will be seen again. Thus instead of a large list search we need only find the first mismarked facet binomial to decide whether a vertex should be output. Furthermore, at each node we keep, we must recompute its facet list every time we pass through it. By comparison the exhaustive search algorithm required us to find facets only once per vertex. One trick that we used to mitigate this re-computation of facets was to save vertices and facet information every time we went up in the tree, so as to avoid recomputing the facets already visited. While this approach means that we are no longer storing just one Gröbner basis, the amount of storage required is still quite small, being bounded by the tree depth. In all the examples listed, the reverse search (with caching) ran in under 750K.

We conclude by drawing attention to the last entry in Table 1 denoted as HM for which A = (247 248 345 15). This was the original counter example found by Hosten and Maclagan (c.f. page 10), using TiGERS, to the conjecture that the maximum valency of a vertex in the state polytope of a corank three matrix is four [ST].

Name d f_{0}  f_{1}  td mn mf md RS  ES
pent 2 8  8  4 4 2 4  0.00  0.00
V23 3 29  45  6 7 4 3  0.02  0.02(0.01)
gti 3 288  467  30 18 4 31 2.30(1.27)  1.50(0.76)
PV33 6 54828  190253 48 36 12 7  (4343.31)  (3731.24)
K5 5 102  255  14 11 5 3  0.36(0.32)  0.28(0.24)
K6 9 195720  56 37 14 4  110111.68(50662.29)
A4 3 20  31  6 8 4 4  0.01( 0.01)  0.01(0.01)
A5 4 114  249  11 14 8 5  0.35( 0.28)  0.25(0.16)
A6 5 488  1394  18 20 12 6  6.78( 4.39)  4.33(2.37)
A7 6 4073  14800 28 29 18 7  239.80( 139.40)  159.96(82.01)
A8 7 25334  111558 41 38 24 8  5010.37( 2732.71)  3624(1867.85)
A9 8 206444 1080981 58 49 32 9  127978.46(67565.22) (71404.29)
A10 9 >578435 -  - - - -  -  -
D2x2 3 108  222  9 10 6 3  0.24( 0.20)  0.23( 0.16)
D2x3 5 4488  14184 19 20 8 3  171.74(97.48)  124.06(71.02)
D3x3 8 >257057
HM 3 904 1546 52 40 5 345 96.72(35.80) 76.08(21.53)

Table 1. TiGERS Timings

References

[AGK] B. Amrhein, O. Gloor and W. Küchlin, On the walk, Theoretical Computer Science 187 (1997) 179–202.

[AF] D. Avis and K. Fukuda, A basis enumeration algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Computational Geometry 8 (1992) 295–313.

[AL] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, American Mathematical Society, 1994.

[BM] D. Bayer and I. Morrison, Standard bases and geometric invariant theory I, Journal of Symbolic Computation 6 (1988) 209–217.

[BFS] L.J. Billera, P. Filliman and B. Sturmfels, Constructions and complexity of secondary polytopes, Advances in Mathematics 83 (1990) 155–179.

[CKM] S.Collart, M.Kalkbrener and D.Mall, Converting bases with the Gröbner walk, Journal of Symbolic Computation 24 (1997) 465-469.

[GKZ] I.M. Gel’fand, M. Kapranov and A. Zelevinsky, Multidimensional Determinants, Discriminants and Resultants, Birkhäuser, Boston, 1994.

[CLO] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Springer-Verlag, New York, Second Edition, 1996.

[Mac] D. Maclagan, Antichains of monomial ideals are finite, Manuscript, 1998.

[MT] D. Maclagan and R. Thomas, On the combinatorics of the toric Hilbert scheme, in preparation.

[MR] T. Mora and L. Robbiano, The Gröbner fan of an ideal, Journal of Symbolic Computation 6 (1988) 183–208.

[PS] I. Peeva and B. Sturmfels, Generic lattice ideals, Journal of the American Mathematical Soceity 11 (1998) 363–373.

[Stu] B. Sturmfels, Gröbner bases and Convex Polytopes, American Mathematical Society, Providence, RI, 1995.

[SST] M. Saito, B. Sturmfels and N. Takayama, Gröbner Deformations of Hypergeometric Differential Equations, in preparation.

[ST] B. Sturmfels and R. Thomas, Variation of cost functions in integer programming, Mathematical Programming 77 (1997) 357-387.

MSRI, 1000 Centennial Drive, Berkeley, CA 94720 E-mail address: birk@msri.org

Dept. of Mathematics, Texas A & M University, College Station, TX 77843

   E-mail address: rekha@math.tamu.edu