Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleThe generic Gröbner walk
Author(s) Komei Fukuda, Anders N. Jensen, Niels Lauritzen, Thomas Sauer
TypeArticle in Journal
AbstractThe Gröbner walk is an algorithm for conversion between Gröbner bases for different term orders. It is based on the polyhedral geometry of the Gröbner fan and involves tracking a line between cones representing the initial and target term order. An important parameter is the explicit numerical perturbation of this line. This usually involves both time and space, demanding arithmetic of integers much larger than the input numbers. In this paper we show how the explicit line may be replaced by a formal line using Robbiano’s characterization of group orders on Q n . This gives rise to the generic Gröbner walk involving only Gröbner basis conversion over facets and computations with marked polynomials. The infinite precision integer arithmetic is replaced by term order comparisons between (small) integral vectors. This makes it possible to compute with infinitesimal numbers and perturbations in a consistent way without introducing unnecessary long integers. The proposed technique is closely related to the lexicographic (symbolic) perturbation method used in optimization and computational geometry. We report on an implementation of our algorithm specifically tailored to computations with lattice ideals.
KeywordsGröbner basis conversion, Polyhedral geometry
URL http://www.sciencedirect.com/science/article/pii/S0747717106001003
JournalJournal of Symbolic Computation
Pages298 - 312
Translation No
Refereed No