Mathematics – Commutative Algebra
Scientific paper
2009-11-04
Mathematics
Commutative Algebra
Scientific paper
Border bases can be considered to be the natural extension of Gr\"obner bases that have several advantages. Unfortunately, to date the classical border basis algorithm relies on (degree-compatible) term orderings and implicitly on reduced Gr\"obner bases. We adapt the classical border basis algorithm to allow for calculating border bases for arbitrary degree-compatible order ideals, which is \emph{independent} from term orderings. Moreover, the algorithm also supports calculating degree-compatible order ideals with \emph{preference} on contained elements, even though finding a preferred order ideal is NP-hard. Effectively we retain degree-compatibility only to successively extend our computation degree-by-degree. The adaptation is based on our polyhedral characterization: order ideals that support a border basis correspond one-to-one to integral points of the order ideal polytope. This establishes a crucial connection between the ideal and the combinatorial structure of the associated factor spaces.
Braun Gábor
Pokutta Sebastian
No associations
LandOfFree
A polyhedral approach to computing border bases 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 A polyhedral approach to computing border bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polyhedral approach to computing border bases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-620394