DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in
Mathematics and Computer Science

March 12 - 16, 2001
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:

Ricky Pollack, New York University, pollack@cims.nyu.edu

Marie-Francoise Roy, University of Rennes, mfroy@maths.univ-rennes1.fr

Micha Sharir, Tel Aviv University, sharir@math.tau.ac.il

Abstracts:

1.

Characterization and Description of Basic Semi-Algebraic
Sets

Carlos Andradas, Universitad Complutense, Madrid

Any semialgebraic set if a (finite) boolean combination of
basic pieces, called basic semialgebraic.  In 1985, L. Brocker
and C. Scheiderer proved that basic semialgebraic subsets of
an algebraic variety $V$ of dimension $V$ can be described
generically (i.e. up to a subset of codimension $\ge1$) by
$d$ inequalities.  This result is in fact at the basis to show
that in fact any semialgebraic subset of $V$ can be described
by a finite number of inequalities depending only on the 
dimension $d$.  However the proofs are not constructive and
very few results are known in trying to decide first if a given
semialgebraic is or not basic (or generically basic) and then
to find a representation of minimal length.  We will survey
both the results by Brocker and Scheiderer focusing mainly on
the scarce attempts to find algorithmic or efficient approaches
to them.



2.

Realization Problems in Geometry 
(distance geometry, matrix completion etc.)

Alexander Barvinok, University of Michigan

Various geometric problems reduce to solving systems of
multivariate real quadratic equations of some special 
structure.  For example, is there a configuration of 
points in Euclidean space of some particular dimension 
with prescribed distances between some points and prescribed
angles between some pair of points? We can derive 
interesting conclusions for such problems by looking at
the combinatorial geometry (facial structure) of the 
cone of positive semidefinite quadratic forms. In 
particular, we observe a "hidden convexity" phenomenon: 
somewhat unexpectedly, some non-convex looking problems turn 
out to be, in fact, convex. This is meant to be a survey talk.



3.

Combinatorial and topological complexity
in computational geometry.

Saugata Basu, Georgia Tech

I will survey some recent results on bounding the combinatorial
and topological complexity of arrangements. I will discuss how
new techniques developed for bounding the toplogical complexity
of semi-algebraic sets lead to new bounds on the combinatorial
complexity in certain situations. Finally, I will talk about
some very recent results refining the classic Oleinik-Petrovsk
-Thom-Milnor bound on the sum of Betti numbers of semi-algebraic 
sets, leading to tight bounds on the individual Betti numbers 
separately.



4.

Combinatorial Characterizations of Algebraic Sets

Isabelle Bonnard, Universite d'Angers

Let X be a compact semialgebraic set. The problem is to
determine if X is homeomorphic to a real algebraic set.   A first
necessary condition was given by Sullivan in 1970: the Euler 
characteristic of the link of X at any point must be even. If the
dimension of  X is strictly lower than 3, this also a sufficient
condition (Akbulut-King,  Benedetti-Dedo, 80's). In dimension 3,
Akbulut and King introduced some  invariants of X, which vanish modulo
2 if and only if $X$ is homeomorphic to  an algebraic set.
Only necessary conditions are known in dimension 4. They have been
given by Parusinski and McCrory, and are formulated in terms of 
algebraically constructible functions.



5.

A look at semidefinite programming duality
and matrix completion problems through real algebraic geometry

Bastiaan J. Braams, Courant Institute, NYU

Convex polygonal cones can be described in two different ways: as
the nonnegative hull of finitely many rays and as the intersection of
finitely many half-spaces.  More precisely, for any $n$ the family of
cones in $R^n$ that can be described as the image of the nonnegative
orthant in $R^p$ for some $p$ under some linear map $R^p\to R^n$ is
the same as the family of cones that can be described as the pre-image
of the nonnegative orthant in $R^q$ for some $q$ under some linear map
$R^n\to R^q$.  In this talk we consider first the related situation
for the case of cones arising in semidefinite programming, replacing
in the previous statement the nonnegative orthants in $R^p$ and $R^q$
by the cones of semidefinite matrices in the space of real symmetric
matrices of orders $p$ and $q$, and considering the family of closures
of images of such cones under linear maps $R^p\to R^n$ and the family
of pre-images under linear maps $R^n\to R^q$.  Using methods from real
algebraic geometry we show that the resulting two families of cones
are not the same if $n\ge3$.  Likewise when instead of the nonnegative
orthant we have the Lorentz cone or a direct sum of Lorentz cones, the
two modes of description yield in general two different families of
cones.  We proceed by characterizing for any family $F$ of
closed convex cones in Euclidean space the minimal family of cones
that contains $F$ and that is complete with respect to the
operations of taking the convex conjugate, taking the closure of the
image under a linear map, and taking the pre-image under a linear map.
We discuss a connection to semidefinite matrix completion problems.




6.

Lower Bounds and Real Algebraic Geometry

Peter Buergisser, University of Paderborn

Many relevant problems in symbolic computation and computational
geometry can be formalized as semi-algebraic computation or decision
problems, to be solved by means of algebraic computation trees. It is a
general paradigm that a complicated combinatorial, geometrical, or
topologial structure of a problem should result in high computational
complexity. This survey talk outlines some of the ideas leading to
lower bounds in terms of degree, Betti numbers, number of faces of an
arrangement etc, emphasizing the role of real algebraic geometry in
this endeavour. We also discuss the impact of randomization on decision
complexity.



7.

Boosting T-constructions

Benoit Chevallier, Toulouse


We are concerned with the isotopical classification of real zero
sets (number of connected components, other Betti numbers,
configurations) of algebraic equations with real coefficients for a
given degree d or a given complexity, and a given number n of variables.

As is known the method of T - construction is efficient to explore such
classifications and accessible to computer science (through its
combinatorial nature : patchworking Newton polyhedra, assigning the
vertices with + or  -  ,  etc ...).

Here we present an extention of the Viro gluing theorem aimed at
smoothing stronger singularities, which is a natural way to explore the
classifications of real algebraic zeros. This extension leads to
polynomials of degrees higher than d, with various shapes of Newton
polyhedra. Those possibilities of ( convex ) shapes can be combined with
T- constructions and increase the later's impact.
We discuss two concrete cases :  ( d =3D 8 , n =3D 2 )  ( still open ) 
(d =3D 4 , n =3D 3 )  ( Hilbert ).



8.

Polynomial root finding using iterated eigenvalue computation

Steven Fortune, Bell Labs

Computing numerical approximations to the roots of a univariate
polynomial is a  classic problem from numerical analysis and symbolic
algebra.  I present a novel  iterative algorithm that combines
floating-point linear algebra with extended- precision arithmetic.  Given
a current estimate of the roots, the algorithm  constructs a
generalization of the companion matrix of the polynomial--actually an
eigenvalue formulation of Lagrange interpolation.  The eigenvalues of the
matrix,  computed in floating-point with standard numerical methods, form
the new estimate  of the roots.  Surprisingly, even though the initial
eigenvalue computations can  be extraordinarily ill-conditioned, the
iteration converges to approximations of the roots accurate to
floating-point precision.  The algorithm has been successfully applied to
very difficult polynomials, e.g. the Wilkinson polynomial of degree 640.
In practice, the algorithm can be an order of magnitude faster than the
best available alternative, the Bini-Fiorentino implementation of
Aberth's iteration.



9.

Pfaffian Complexity

Andre Gabrielov, Purdue University

Pfaffian functions  are real analytic functions 
satisfying triangular systems of Pfaffian (first
order partial differential) equations with polynomial 
coefficients. In the real domain, these functions, and 
the corresponding semi- and sub-Pfaffian sets, are
characterized by global finiteness properties of 
polynomials and real semi-algebraic sets. This 
allows one to establish efficient upper bounds on 
the complexity of different algebraic and geometric
operations with these functions and sets.

One of the most important applications of the Pfaffian 
theory is in the real algebraic geometry of "fewnomials" 
- polynomials defined by simple formulas, possibly of 
a high degree. The complexity of operations with these 
polynomials in many cases can be estimated from above in 
terms of the complexity of these simple formulas, independent 
of their degree.  

An overview of the algorithms for operations 
on Pfaffian and fewnomial functions and sets, their 
complexity, and unsolved problems will be presented.




10.

How difficult is to compute the open description of an open
semialgebraic set?

Laureano Gonzalez-Vega, University of Cantabria

It is well known that the semialgebraic set of the monic polynomials
of degree four without real roots is open and that it
can be described as a finite  union of semialgebraic sets explicitely
open (ie defined only by open polynomial conditions). We show, first,
how  this open description can be computed (answering a question
posed by E. Becker) and, second,  why this problem, in general, is
very difficult to solve.



11.

Combinatorial Methods for Constructing Real 
Algebraic Varieties

Bertrand Haas, State University of Michigan

We will review Viro patchworking construction of 
T-hypersurfaces and see some examples of problems 
for which this technique is usefull and some for 
which other techniques must be used.  In particular 
we will see a new "trick" to construct fewnomial 
systems with many roots, which give a family of 
counter-examples to Kouchnirenko's conjecture.


12.

Challenges and Issues in Robust Geometric Computation

Chen Li, Courant Institute, NYU

In the last two decades, research in computational geometry
has produced an impressive wealth of efficient algorithms.
But the rate of technology transfer to applications lags
behind.  One important reason for this is the well-known
numerical non-robustness problem that often arises in the
implementation of algorithms.

In this talk, I will survey recent research efforts in robust
geometric computation.  My main focus will be on the challenges
and issues in Exact Geometric Computation (EGC), a general approach
for removing non-robustness.  The main issue in EGC is efficiency
and various techniques have been proposed.  An example is the 
computation of effective root bounds.  I will describe some of 
our theoretical as well as experimental efforts.  We have 
developed an easy-to-use C++ library called the Core Library
to make EGC techniques widely available to programmers.  An
unexpected application of this library is in automated proving
of elementary geometry theorems.



13.

Computational Approaches to Representation Theorems for Finitely
Generated Real Algebras

Vicki Powers, Emory University
This work is joint with Dionne Bailey.  

Schmudgen's Theorem says that a real polynomial f which is positive 
on a basic closed semialgebraic set S is in the preorder generated by 
the polynomials defining the set,i.e., f has a representation as a 
finite sum of products of sums of squares and the  polynomials defining 
S.  Such a representation can be thought of as a  "certificate of 
positivity" from which the positivity of f can be deduced  immediately.  
The proof uses functional analysis methods and is not  constructive,
for example no information on the degree of the "output data" or a 
method for finding a representation can be deduced from the proof. 
T. Wormann found an algebraic proof using the Kadison-Dubois theorem, 
but  again the proof is not constructive.
Recently, M. Schweighofer has found a constructive approach to the
theorem, using P`olya's Theorem for homogeneous polynomials positive on
the standard simplex.  In recent work, we have used the approach of
Schweighofer to give a constructive proof of the Kadison-Dubois Theorem
for finitely generated real algebras.  We can then apply this to give  a
constructive proof of a recent result of M. Marshall which generalizes
Schm\"udgen's Theorem to the non-compact case.  We will also discuss a
similar approach to very recent work of Jacobi and Prestel on "linear"
representations, i.e., representations which do not involve products of
two or more of the polynomials defining the semialgebraic set.



14.

Patterns of dependence among powers of polynomials

Bruce Reznik, University of Illinois

Let $F =3D\{f_1,\dots,f_r\}$ be a family of homogeneous
polynomials over $\bf C$, of degree $d$ in $n$ variables, and let
$$T(F) =3D  \{m \in {\bf N}: \{f_1^m,\dots,f_r^m\}\quad \hbox{is linearly
dependent} \}.$$ are interested in knowing the possible sets which can occur 
as $T(F)$ for fixed $r$, $n$ and $d$. This problem can be completely
answered when $r \le 3$ (Fermat's Last Theorem for polynomials), when
$d=3D1$ (Serret's Theorem) and when $(r,n,d) =3D (4,2,2)$ (related to very
classical number theory). A particularly interesting example in this last
case is  $$ f_k(x,y) =3D i^k x^2 + \sqrt 2 x y - i^{-k} y^2,\qquad 1\le k
\le 4, $$ for which $T(F) =3D \{1,2,5\}$. Combinatorists and geometers may
enjoy the fact that,  if we write $f_k(x,y) =3D i^k(x - \alpha_k y)
(x - \beta_ky)$, and then take the usual stereographic projection of the 
extended complex plane onto the unit sphere, we find that the pairs
$(\alpha_k,\beta_k)$ go to antipodal vertices of an inscribed cube.
Commutative algebraists may enjoy that the existence of such a family is 
closely related to the fact that $X_1^5 + X_2^5 + X_3^5 +
X_4^5$ is contained in the ideal generated by $X_1 + X_2 + X_3 +
X_4$ and  $X_1^2 + X_2^2 + X_3^2 + X_4^2$. (However, when $(r,n,d) =
(4,2,2)$, there is no set of {\it real} forms with $T =3D \{1,2,5\}$.)
The talk will have more questions than answers and more examples than
theorems.



15.

Efficient Agorithms Based on the Critical 
Point Method

Fabrice Rouillier, INRIA Lorrainne

Finding one point on each semi-algebraically connected
component of a real algebraic variety is a fundamental 
problem of computational real algebraic geometry. 
Although numerous studies have been done on the
subject, only a few number of efficient implementations 
exist.

By studying the critical points of the restriction 
to the variety of the distance function to one well 
chosen point, one can compute a set of zero-dimensional
systems whose zeros contain at least one point on each 
semi-algebraically connected component of the studied variety. 

In a theoretical point of view, the best known complexity bound 
for the problem of finding one point on each semi-algebraically 
connected component of a real algebraic variety have been obtained 
using such strategies.

In a practical point of view, the various tricks used for 
keeping a good complexity such as using sum of squares 
(for working with on equation instead of a system) or 
Puiseux series as ground field (for working with smooth 
and/or compact varieties) have a dramatic effect on the
practical behavior of the method.

Taking in acount the current capabilities of computer 
algebra systems, we show how to compute efficiently a 
set of zero-dimensional systems whose zeros contain at 
least one point on each semi-algebraically connected 
component of the studied variety, without any assumption 
neither on the variety (smoothness or compactness for example) 
nor on the system of equations which define it.

From the output of our algorithm(s), one can then apply, 
for each computed zero-dimensional system, any symbolic 
or numerical algorithm for counting or approximating the 
real solutions. The practical efficiency of our method 
is due to the fact that we do not apply any infinitesimal
deformations, unlike the existing methods based on a similar 
strategy.



16.

What Can Computational Geometry and Real Algebraic Geometry Contribute to each other.

Micha Sharir, Tel Aviv University and NYU

This talk describes various topics that lie at the interface
between the two disciplines, such as construction and analysis of 
arrangements of algebraic surfaces, lower bound proofs, robust 
computations, and more. We mostly review the (accomplished and
potential) contributions of real algebraic geometry to computational
geometry,  but also mention some interactions in the other direction
(e.g., separating the `combinatorial' from the `algebraic' complexity
of semialgebraic sets).



17.

Enumerative Real Algebraic Geometry

Frank Sottile, University of Massachusetts

Enumerative Geometry is concerned with the number of
solutions to a structured system of polynomial equations,
when the structure comes from geometry.  

Enumerative real algebraic geometry is concerned with 
real solutions to such systems, particularly a priori 
information on their number.  Recent results in this 
area have, often as not, uncovered new and unexpected 
phenomena, and it is far from clear what to expect in general.  
Nevertheless, some themes are emerging. My intention in
this talk is to describe the current state of knowledge, 
to indicate these themes, and to suggest lines of future 
research.



18.

Combinatorial Roadmaps in Configuration Spaces of Simple Planar
Polygons

Ileana Streinu, Smith College

The configuration space of simple planar polygons with fixed
edge lengths is connected, and a roadmap can be constructed
combinatorially using special one-degree-of-freedom mechanisms induced
by pseudo-triangulations with a convex hull edge removed.



19.

Minimizing Polynomial Functions

Bernd Sturmfels, University of California at Berkeley

We compare algorithms for global
optimization of polynomial functions. Our 
experiments show that methods from computational algebra (Grobner
bases, resultants, homotopy methods) are dramatically outperformed by a
relaxtion technique, first suggested by N.Z.~Shor, which involves sums of 
squares and semidefinite programming. This is a joint project with Pablo 
Parrilo, based on work reported in Pablo's thesis,
http://www.cds.caltech.edu/~pablo/




20.

Algorithmic line problems in 3-space and their enumerative
geometry

Thorsten Theobald, Technische Universitaet Muenchen

A variety of tasks in computational geometry (e.g, computing
stabbing lines or visibility computations with moving viewpoints) can be
reduced to purelygeometric problems in the space of lines in
$\mathbb{R}^3$. Since algorithmic solutions are based on characterizing
certain extreme situations, these problems naturally lead to problems of
enumerative geometry. In particular, it is necessary to compute the
common tangent lines to a small number of given bodies. In this talk, we
investigate the underlying enumerative geometry problems when the bodies
are combinations of polytopes and balls. In particular, we compute some
tight bounds for the maximum number of common tangent lines in these
cases.



21.

Thierry Zell, Purdue University

On the number of connected components of the relative closure of a
semi-Pfaffian family.

In this talk, an explicit bound is given for the number of
connected components of a limit set $(X,Y)_0$ in terms of the 
Pfaffian complexity of $X$ and $Y.$=20

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage