# 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

## The impact of estimation errors on CDO pricing

Another interesting, nicely written paper about valuating and pricing CDOs is “The Economics of Structured Finance” from Coval, Jurek, and Stafford which just appeared in the Journal of Economic Perspectives. It nicely complements the paper of Arora, Barak, Brunnermeier, and Ge titled “Computational Complexity and Information Asymmetry in Financial Products” (see also here). The authors argue that already small estimation errors in correlation and probability of default (of the underlying loans) can have devastating effect on the overall performance of a tranche. Whereas the senior tranches remain quite stable in the presence of estimation errors, the overall rating of the junior and mezzanine tranches can be greatly affected. Intuitively this is clear, as the junior and the mezzanine tranches act as a cushion for the senior tranches (and in turn the junior tranches are a protection of the mezzanine tranches). What is not so clear though at first is that this effect is so pronounced, i.e., smallest estimation errors lead to a rapid decline in credit quality of these tranches. In fact, what happens here is that the junior and mezzanine tranches pay the price for the credit enhancement of the senior tranches. And the stability of the latter with respect to estimation errors comes at the expense of highly sensitive junior and mezzanine tranches.

This effects becomes even more severe when considering CDO^2, where the loans of the junior and mezzanine tranches are repackaged again. These structures possess a very high sensitivity to slightest variations or estimation errors in the probability of default or correlation.

In both cases, slight impressions in the estimation can have severe impacts. But also, considering it the other way around, slight changes in the probability of default or the correlation due to changed economic conditions can have devastating effect on the value of the lower prioritized tranches.

So if you are interested in CDOs, credit enhancement, and structured finance you should give it a look.

Written by Sebastian

December 6, 2009 at 4:32 pm