2009/11/04 by Gábor Braun, Sebastian Pokutta, Braun, Gábor +1
Computer Science · Mathematics · #12Y05 #13P10 #65H10 #68R05 #90C27 #90C57 #Algebraic Geometry (math.AG) #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #FOS: Mathematics #Formal Methods in Verification #Polynomial and algebraic computation #math.AC #math.AG #msc:12Y05 #msc:13P10 #msc:65H10 #msc:68R05 #msc:90C27 #msc:90C57
paper · pdf · doi:10.48550/arxiv.0911.0859
openalex publication_date 2009/11/04 · arxiv created 2010/02/05 · arxiv updated 2010/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Border bases can be considered to be the natural extension of Gröbner bases that have several advantages. Unfortunately, to date the classical border basis algorithm relies on (degree-compatible) term orderings and implicitly on reduced Gröbner bases. We adapt the classical border basis algorithm to allow for calculating border bases for arbitrary degree-compatible order ideals, which is independent from term orderings. Moreover, the algorithm also supports calculating degree-compatible order ideals with 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.