|
C.6.2.1 The algorithm of Conti and Traverso
The algorithm of Conti and Traverso (see [CoTr91])
computes via the
extended matrix ,
where is the unity matrix. A lattice basis of is
given by the set of vectors
, where
is the -th row of and the -th coordinate vector. We
look at the ideal in
corresponding to
these vectors, namely
We introduce a further variable and adjoin the binomial to the generating set of , obtaining an ideal in the polynomial ring . is saturated w.r.t. all variables because all variables are invertible modulo . Now can be computed from by eliminating the variables . 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).
|