Home Online Manual
Top
Back: Pottier
Forward: Di Biase and Urbanke
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.3 The algorithm of Hosten and Sturmfels

The algorithm of Hosten and Sturmfels (see [HoSt95]) allows to compute $I_A$ without any auxiliary variables, provided that $A$ contains a vector $w$ with positive coefficients in its row space. This is a real restriction, i.e., the algorithm will not necessarily work in the general case.

A lattice basis $v_1, \ldots, v_r$ is again computed via the LLL-algorithm. The saturation step is performed in the following way: First note that $w$ induces a positive grading w.r.t. which the ideal

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

is homogeneous corresponding to our lattice basis. We use the following lemma:

Let $I$ be a homogeneous ideal w.r.t. the weighted reverse lexicographical ordering with weight vector $w$ and variable order $x_1 > x_2 > \ldots > x_n$. Let $G$ denote a Groebner basis of $I$ w.r.t. this ordering. Then a Groebner basis of $(I:x_n^\infty)$ is obtained by dividing each element of $G$ by the highest possible power of $x_n$.

From this fact, we can succesively compute

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

in the $i$-th step we take $x_i$ as the smallest variable and apply the lemma with $x_i$ instead of $x_n$.

This procedure involves $n$ Groebner basis computations. Actually, this number can be reduced to at most $n/2$(see [HoSh98]), and each computation -- except for the first one -- proves to be simple and fast in practice.