Mathematics and Computer Science

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

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

Contacting the Center

Document last modified on March 8, 2001.