Sebastian Pokutta's Blog

Mathematics and related topics

Characterizing border bases using polyhedral combinatorics

with one comment

Gábor Braun from the Hungarian Academy of Sciences and I just managed to finish our article “Border bases and order ideals: a polyhedral characterization” which is an extension of our former work that was restricted to degree-compatible order ideals. The article addresses an old problem in computer algebra that Gröbner bases and border bases are usually computed with respect to a term ordering (basically a total ordering on the monomials that is compatible with multiplication). Whereas for Gröbner bases this makes sense, for border bases, relying on a (degree-compatible) term ordering excludes a large number of potential border bases though, as the associated order ideal cannot be obtained by a term ordering.

More precisely, for a given zero-dimensional I \subseteq K[X], a border basis arises from a special decomposition of a polynomial ring K[X] into K[X] = I \oplus \langle \mathcal O \rangle_K (as vector spaces) where \mathcal O is subset of the monomials with the property that whenever m_1 \mid m_2 and m_2 \in \mathcal O then it follows that m_1 \in \mathcal O — a subset with this property is an order ideal. Every order ideal that induces such a decomposition is in one-to-one correspondence with a border basis (as a consequence of the directness of the sum). In case the order ideal and the associated decomposition is induced by a Gröbner basis and its underlying term ordering, we can compute a border basis using the classical border basis algorithm (a specialization of Mourrain’s generic algorithm). We do not have to worry about any combinatorial complications here.

The situation completely changes when we want to compute border bases for arbitrary order ideals. First of all, not every order ideal does actually support a border basis. For a given order ideal that supports a border basis though, one can adapt the classical border basis algorithm to be able to compute the border basis (with respect to this order ideal) as well. Thus the main problem that we are facing is to identify those order ideals that do support a border basis (of a given zero-dimensional ideal). The combinatorial challenge that we are facing then is that we have to ensure two opposite conditions: On the one hand, we need to ensure that our complementary basis forms an order ideal and at the same time we have to ensure that the decomposition is direct, i.e., we obtain constraints on the dimension and linear independence of certain sub vector spaces. This gives rise to a nice combinatorial problem that can be captured using polyhedral combinatorics. In fact, for a given zero-dimensional I one can define a 0/1 polytope, the order ideal polytope, whose integral points are in one-to-one correspondence with all those order ideals that do actually support a border basis. We were also able to show that optimizing over the integral hull of the order ideal polytope is NP-hard and thus it is unlikely that we can obtain a nice characterization of the integral points. This underlines the fact that lots of the combinatorial structure in an ideal is reflected in the factor spaces and the complementary bases.


Written by Sebastian

December 8, 2009 at 5:39 pm

One Response

Subscribe to comments with RSS.

  1. […] basis which is a mere basis transformation from a linear algebra point of view (see also my previous post for some more details). Here are the […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: