
C.6.2.3 The algorithm of Hosten and SturmfelsThe algorithm of Hosten and Sturmfels (see [HoSt95]) allows to compute without any auxiliary variables, provided that contains a vector 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
is again computed via the
LLLalgorithm.
The saturation step is performed in the following way:
First note that induces a positive grading w.r.t. which the ideal
is homogeneous corresponding to our lattice basis. We use the following lemma: Let be a homogeneous ideal w.r.t. the weighted reverse lexicographical ordering with weight vector and variable order . Let denote a Groebner basis of w.r.t. this ordering. Then a Groebner basis of is obtained by dividing each element of by the highest possible power of .
From this fact, we can succesively compute
in the th step we take as the smallest variable and apply the lemma with instead of . This procedure involves Groebner basis computations. Actually, this number can be reduced to at most (see [HoSh98]), and each computation  except for the first one  proves to be simple and fast in practice.
