Skip to main content
main-content
Top

About this book

Recent advances in both the theory and implementation of computational algebraic geometry have led to new, striking applications to a variety of fields of research. The articles in this volume highlight a range of these applications and provide introductory material for topics covered in the IMA workshops on "Optimization and Control" and "Applications in Biology, Dynamics, and Statistics" held during the IMA year on Applications of Algebraic Geometry. The articles related to optimization and control focus on burgeoning use of semidefinite programming and moment matrix techniques in computational real algebraic geometry. The new direction towards a systematic study of non-commutative real algebraic geometry is well represented in the volume. Other articles provide an overview of the way computational algebra is useful for analysis of contingency tables, reconstruction of phylogenetic trees, and in systems biology. The contributions collected in this volume are accessible to non-experts, self-contained and informative; they quickly move towards cutting edge research in these areas, and provide a wealth of open problems for future research.

Table of Contents

Frontmatter

Polynomial Optimization on Odd-Dimensional Spheres

Abstract
The sphere S 2d-1 naturally embeds into the complex affine space ℂd simplify the known Striktpcsitivstellensätze, when the supports are resticted to semi-algebraic subsets of odd dimensional spheres. We also illustrate the subtleties involved in trying to control the number of squares in a Hermitian sum of squares.
John P. D’Angelo, Mihai Putinar

Engineering Systems and Free Semi-Algebraic Geometry

Abstract
This article sketches a few of the developments in the recently emerging area of real algebraic geometry (in short RAG) in a free* algebra, in particular on “noncommutative inequalities”. Also we sketch the engineering problems which both motivated them and are expected to provide directions for future developments. The free* algebra is forced on us when we want to manipulate expressions where the unknowns enter naturally as matrices. Conditions requiring positive definite matrices force one to noncommutative inequalities. The theory developed to treat such situations has two main parts, one parallels classical semialgebraic geometry with sums of squares representations (Positivstellensatze) and the other has a new flavor focusing on how noncommutative convexity (similarly, a variety with positive curvature) is very constrained, so few actually exist.
Mauricio C. De Oliveira, J. William Helton, Scott A. Mccullough, Mihai Putinar

Algebraic Statistics and Contingency Table Problems: Log-Linear Models, Likelihood Estimation, and Disclosure Limitation

Abstract
Contingency tables have provided a fertile ground for the growth of algebraic statistics. In this paper we briefly outline some features of this work and point to open research problems. We focus on the problem of maximum likelihood estimation for log-linear models and a related problem of disclosure limitation to protect the confidentiality of individual responses. Risk of disclosure has often been measured either formally or informally in terms of information contained in marginal tables linked to a log-linear model and has focused on the disclosure potential of small cell counts, especially those equal to 1 or 2. One way to assess the risk is to compute bounds for cell entries given a set of released marginals. Both of these methodologies become complicated for large sparse tables. This paper revisits the problem of computing bounds for cell entries and picks up on a theme first suggested in Fienberg [21] that there is an intimate link between the ideas on bounds and the existence of maximum likelihood estimates, and shows how these ideas can be made rigorous through the underlying mathematics of the same geometric/algebraic framework. We illustrate the linkages through a series of examples. We also discuss the more complex problem of releasing marginal and conditional information. We illustrate the statistical features of the methodology on two examples and then conclude with a series of open problems.
Adrian Dobra, Stephen E. Fienberg, Alessandro Rinaldo, Aleksandra Slavkovic, Yi Zhou

Using Invariants for Phylogenetic Tree Construction

Abstract
Phylogenetic invariants are certain polynomials in the joint probability distribution of a Markov model on a phylogenetic tree. Such polynomials are of theoretical interest in the field of algebraic statistics and they are also of practical interest-they can be used to construct phylogenetic trees. This paper is a self-contained introduction to the algebraic, statistical, and computational challenges involved in the practical use of phylogenetic invariants. We survey the relevant literature and provide some partial answers and many open problems.
Nicholas Eriksson

On the Algebraic Geometry of Polynomial Dynamical Systems

Abstract
This paper focuses on polynomial dynamical systems over finite fields. These systems appear in a variety of contexts, in computer science, engineering, and computational biology, for instance as models of intracellular biochemical networks. It is shown that several problems relating to their structure and dynamics, as well as control theory, can be formulated and solved in the language of algebraic geometry.
Abdul S. Jarrah, Reinhard Laubenbacher

A Unified Approach to Computing Real and Complex Zeros of Zero-Dimensional Ideals

Abstract
In this paper we propose a unified methodology for computing the set V K (I) of complex (K = ℂ) or real (K = ℝ) roots of an ideal R[x], assuming Vk (I ) is finite. We show how moment matrices, defined in terms of a given set of generators of the ideall, can be used to (numerically) find not only the real variety V R (I), as shown in the Authors’ previous work, but also the complex variety V c (I), thus leading to a. unified treatment of the algebraic and real algebraic problem. In contrast to the real algebraic version of the algorithm, the complex analogue only uses basic numerical linear algebra because it does not require positive semidefiniteness of the moment matrix and so avoids semidefinite programming techniques. The links between these algorithms and other numerical algebraic methods arc outlined and their stopping criteria are related.
Jean Bernard Lasserre, Monique Laurent, Philipp Rostalskl

Sums of Squares, Moment Matrices and Optimization Over Polynomials

Abstract
We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background.
Monique Laurent

Positivity and Sums of Squares: A Guide to Recent Results

Abstract
This paper gives a survey, with detailed references to the literature, on recent developments in real algebra and geometry concerning the polarity between positivity and sums of squares. After a review of foundational material, the topics covered are Positiv- and Nichtnegativstellensatze, local rings, Pythagoras numbers, and applications to moment problems.
Claus Scheiderer

Noncommutative Real Algebraic Geometry Some Basic Concepts and First Ideas

Abstract
We propose and discuss how basic notions (quadratic modules, positive elements, semialgebraic sets, Archimedean orderings) and results (Positivstellensätze) from real algebraic geometry can be generalized to noncommutative *-algebras. A version of Stengle's Positivstellensatz for n X n matrices of real polynomials is proved.
Konrad Schmüdgen

Open Problems in Algebraic Statistics

Abstract
Algebraic statistics is concerned with the study of probabilistic models and techniques for statistical inference using methods from algebra and geometry. This article presents a list of open mathematical problems in this emerging field, with main emphasis on graphical models with hidden variables, maximum likelihood estimation, and multivariate Gaussian distributions. These are notes from a lecture presented at the IMA in Minneapolis during the 2006/07 program on Applications of Algebraic Geometry.
Bernd Sturmfels

Backmatter

Additional information

Premium Partner

    Image Credits