COCOA VIII

COmputational COmmutative Algebra
and
International School on Computer Algebra

Jesus De Loera

Toric Rational Functions and their applications in Combinatorics, Statistics and Optimization

A large variety of problems in Computer algebra, Combinatorics, Statistics, Optimization can be formulated in the language of toric ideals related to polyhedra. Examples of these are: Hilbert functions of monomial rings, computing Ehrhart polynomials and volumes of polytopes, Counting contingency tables, Solving hard knapsack problems.

Recently there has been a realization that the fastest and most compact representation of all these problems is using rational functions as a data structure. Barvinok's work first showed us that when the number of variables/dimension is fixed the computational complexity of all these problems is polynomial. We showed that in practice this approach is also quite fast and able to crack rather large concrete problems.

In this talk we explain the new approach, demostrate our new software LATTE, and explain several fascinating computer algebra challenges arising from this. This is joint work with Raymond Hemmecke and Ruriko Yoshida.

Gregor Kemper

Invariant Theory and Computer Vision

This talk is about joint work with Mireille Boutin, which originated in the following question: Is a configuration of $n$ points in Euclidean space uniquely determined (up to rigid motions and renumbering of the points) by the distribution of distances between pairs of points? As we will see by examples, the answer is NO in general, even in ${\mathbf R}^2$. However, the good news is that point configurations which are not reconstructible from their distribution of distances are rare, in the sense that the reconstructible configurations form a Zariski-dense subset. This result has obvious applications in computer vision. In the talk the question and its answer will be put into the context of invariant theory and computer algebra.

There are a number of other groups which occur naturally in computer vision, such as the affine special linear group or the projective group. We will be particularly interested in the group of affine transformations with determinant $\pm 1$. Here the distribution of areas of subtriangles (or more generally volumes of sub-$m$-simplices in $m$-dimensional space) offers itself as a candidate for an invariant which allows reconstruction up to the group action and renumbering. Again, there are counter examples, but the nice result is that most point configurations are reconstructible in that sense.

Martin Kreuzer

Multigraded Structures in Polynomial Rings

In the first part of the talk, I will recall some foundations for multigraded computations. We use Z^m-gradings on polynomial rings which are given by a matrix whose columns are the multidegrees of the indeterminates. In order to be useful for explicit computer calculations, the gradings under consideration have to be positive in the sense that there is no infinite decreasing chain of degrees of non-zero polynomials.

Then I will present a suitable version of the Buchberger algorithm for computing multihomogeneous Gröbner bases and discuss several variants which compute multihomogeneous minimal systems of generators or truncated Gröbner bases. These algorithms apply to graded submodules of finitely generated graded free modules over polynomial rings.

It is well-known that Buchberger's algorithm also allows us to compute the syzygy module of a tuple of multihomogeneous vectors. In order to compute a minimal homogeneous presentation of a multigraded module, it appears at first sight to be necessary to compute a second Gröbner basis in order to minimalize the generators of the syzygy module. The main topic of the talk is to show that there exists a better method.

This method is based on the concept of idealizing a module, i.e. representing it as an ideal in a suitable ring. In the case of multigraded submodules, we can find an explicit description of their idealization. Then I will explain the behaviour of multihomogeneous Gröbner bases and minimal multihomogeneous systems of generators under this process.

The final step is the possibility to idealize not just the multigraded submodule, but a multihomogeneous presentation of such a module. After performing such an idealization in an explicit way, we are able to compute the minimal multihomogeneous presentation using a single application of the multihomogeneous Buchberger algorithm with minimalization. This computation corresponds to the classical horizontal strategy for computing minimal presentations.

Continuing these efforts to compactify the computation of minimal multihomogeneous presentations and minimal multigraded free resolutions, I will end the talk by introducing recent work by Massimo Caboara and Carlo Traverso which allows us to compute the whole multigraded resolution in a polynomial ring which contains only three additional indeterminates.

Pablo Parillo

Real Algebra and Convex Optimization

Gerhardt Pfister

Computer Algebra and Group Theory

dvi file

Mike Stillman

The Algebraic Geometry of Bayesian Networks

Rekha Thomas

Simplicial Complexes, Generic Initial Ideals and Combinatorics

The results that will be presented in this talk were motivated by the technique of algebraic shifting, an operation on simplicial complexes introduced by Gil Kalai that converts a given simplicial complex into a combinatorially simpler (shifted) complex while preserving several invariants. There are two forms of shifting: symmetric shifting in the polynomial ring and exterior shifting in the exterior algebra. Both involve computing the reverse lex generic initial ideal (gin) of the Stanley-Reisner ideal of the input complex.