Top
Back: Algorithms
Forward: Pottier
FastBack: Gauss-Manin connection
FastForward: Buchberger algorithm
Up: Algorithms
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

C.6.2.1 The algorithm of Conti and Traverso

The algorithm of Conti and Traverso (see [CoTr91]) computes $I_A$ via the extended matrix $B=(I_m\vert A)$, where $I_m$ is the $m\times m$ unity matrix. A lattice basis of $B$ is given by the set of vectors $(a^j,-e_j)\in Z\!\!\! Z^{m+n}$, where $a^j$ is the $j$-th row of $A$ and $e_j$ the $j$-th coordinate vector. We look at the ideal in $K[y_1,\ldots,y_m,x_1,\ldots,x_n]$ corresponding to these vectors, namely

\begin{displaymath}I_1=<y^{a_j^+}- x_j y^{a_j^-} \vert j=1,\ldots, n>.\end{displaymath}

We introduce a further variable $t$ and adjoin the binomial $t\cdot y_1\cdot\ldots\cdot y_m -1$ to the generating set of $I_1$, obtaining an ideal $I_2$ in the polynomial ring $K[t, y_1,\ldots,y_m,x_1,\ldots,x_n]$. $I_2$ is saturated w.r.t. all variables because all variables are invertible modulo $I_2$. Now $I_A$ can be computed from $I_2$ by eliminating the variables $t,y_1,\ldots,y_m$.

Because of the big number of auxiliary variables needed to compute a toric ideal, this algorithm is rather slow in practice. However, it has a special importance in the application to integer programming (see Integer programming).

Top Back: Algorithms Forward: Pottier FastBack: Gauss-Manin connection FastForward: Buchberger algorithm Up: Algorithms Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 4.3.2, 2023, generated by texi2html.