Home Online Manual
Top
Back: Toric ideals and integer programming
Forward: Algorithms
FastBack: Gauss-Manin connection
FastForward: Integer programming
Up: Toric ideals and integer programming
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

C.6.1 Toric ideals

Let $A$ denote an $ m \times n $ matrix with integral coefficients. For $u \in Z\!\!\! Z^n$, we define $u^+,u^-$ to be the uniquely determined vectors with nonnegative coefficients and disjoint support (i.e., $u_i^+=0$ or $u_i^-=0$ for each component $i$) such that $u=u^+-u^-$. For $u\geq 0$ component-wise, let $x^u$ denote the monomial $x_1^{u_1}\cdot\ldots\cdot x_n^{u_n}\in K[x_1,\ldots,x_n]$.

The ideal

\begin{displaymath}I_A:=(x^{u^+}-x^{u^-} \vert u\in\ker(A)\cap Z\!\!\! Z^n)\ \subset K[x_1,\ldots,x_n] \end{displaymath}

is called a toric ideal.

The first problem in computing toric ideals is to find a finite generating set: Let $v_1, \ldots, v_r$ be a lattice basis of $\ker(A)\cap Z\!\!\! Z^n$ (i.e, a basis of the $Z\!\!\! Z$-module). Then

\begin{displaymath}I_A:=I:(x_1\cdot\ldots\cdot x_n)^\infty \end{displaymath}

where

\begin{displaymath}I=<x^{v_i^+}-x^{v_i^-}\vert i=1,\ldots,r> \end{displaymath}

The required lattice basis can be computed using the LLL-algorithm ( system, see see [Coh93]). For the computation of the saturation, there are various possibilities described in the section Algorithms.

C.6.2 Algorithms  Various algorithms for computing toric ideals.
C.6.3 The Buchberger algorithm for toric ideals  Specializing it for toric ideals.