The generic Groebner walk

Mathematics – Commutative Algebra

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

The Groebner walk is an algorithm for conversion between Groebner bases for different term orders. It is based on the polyhedral geometry of the Groebner fan and involves tracking a line between cones representing the initial and target term order. An important parameter is 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 Groebner walk involving only Groebner basis conversion over facets and computations with marked polynomials. The proposed technique is closely related to the lexicographic (symbolic) perturbation method used in optimization and computational geometry. We report on computations with toric ideals, where a version of our algorithm in certain cases computes test sets for hard integer knapsack problems significantly faster than the Buchberger algorithm.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

The generic Groebner walk does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The generic Groebner walk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The generic Groebner walk will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-593876

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.