TBA
A classic result in real algebraic geometry due to Oleinik-Petrovsky, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers.
We prove better bounds on the individual Betti numbers of basic semi-algebraic sets, as well as on the sum of the i-th Betti numbers over all realizations of sign conditions of a set of real polynomials. As a corollary we obtain a polynomial bound on the highest Betti numbers of basic semi-algebraic sets defined by quadratic inequalities.
Our technique for proving these bounds involves using certain spectral sequences related to the generalized Mayer-Vietoris exact sequence. The spectral sequence method also has algorithmic consequences for designing efficient algorithms for computing the Betti numbers of a set defined by polynomial inequalities. I will also discuss some of these algorithmic implications.
The Viro Method is a powerful construction method for real non-singular algebraic hypersurfaces with prescribed topology. A combinatorial version of the Viro method is called combinatorial patchworking and arises when the considered subdivisions are triangulations. B. Sturmfels has generalized combinatorial patchworking to the case of real complete intersections. We extend this result to generalizing the Viro method to the case of real complete intersections.
I will discuss applications of residues, in one and many variables, to computational questions. Topics will include: classical and multidimensional Newton identities for the power sums of the roots of a polynomial system; Erhart reciprocity; toric residues and the recent Toric Residue Mirror Conjecture proposed by V. Batyrev and E. Materov.
Chemical reactions are described by a sparse polynomial system. These polynomial systems have additional structure because the coefficient matrix is given by adjacency and incidence matrices of a bipartite graph and a directed graph. First we will show which influence the lattice has on positive solutions. Then I will introduce the deformed toric variety and the cone. In analogy to the polyhedral homotopy method certain constants define a toric deformation.
[1] K. Gatermann, B. Huber, A family of sparse polynomial systems arising in chemical reaction systems. Journal of Symbolic Computation 33(3), 275-305, 2002.
[2] K. Gatermann, Counting stable solutions of sparse polynomial systems in chemistry. Contemporary Math. Volume 286, Symbolic Computation: Solving Equations in Algebra, Geometry, and Engineering, Editors: E. Green, S. Hosten, R. Laubenbacher, V. Powers, AMS, Providence, Rhode Island, 53--69, 2001.
We examine a system of equations arising in biophysics whose solutions represent the stable positions of N conical proteins embedded in a cell membrane. Symmetry considerations motivate two equivalent refomulations of the system which allow the complete classification of solutions for small N<13. The occurrence of regular geometric patterns in these solutions suggests considering a simpler system describing solutions involving regular polygons. This leads to the detection of solutions for larger N up to 280. We use recent techniques of Groebner bases computation for solving non linear systems.
This talk will highlight several problems dealing with both finite and infinite free resolutions, most of which show the state of our ignorance, both in what we know and current examples. If time permits, I will try to link some of these problems to questions about primary decompositions.
This talk will present an explicit formula for computing the resultant of any three polynomials in two variables, all with the same support. The matrix is a hybrid of Sylvester and Bezout types. We make use of some exciting new tools in exterior algebras developed by Eisenbud, Floystad and Schreyer, and apply them to the toric setting.
Implicitization and parameterization are two fundamental problems in computational algebraic geometry. Implicitization is the conversion of parametric equations of a geometric object to an implicit equation. The opposite process is referred to as parameterization and is in general a harder problem to address.
Both problems have immediate practical applications to computer-aided design where one typically requires thousands of conversions between implicit and parametric forms of equations of curves and surfaces in real time. Thus it is important to have good algorithms at hand for both problems.
Many efficient and robust algorithms for implicitization and parameterization have been developed in Symbolic Computation using a wide variety of techniques such as resultants, Grobner bases, characteristic sets, perturbations, multidimensional Newton formulae, symmetric functions, elimination, moving frames, linear systems, integral bases, polynomial factorization and adjoint functions. These algorithms provide constructive answers to the implicitization and parameterization problems and have been implemented in commercial and freely available Computer Algebra Systems as well as in stand-alone programs. Some of the available algorithms are suitable for special categories of curves and surfaces only.
We developed a new algorithm to perform implicitization of curves, surfaces and hypersurfaces. The algorithm is based in an interpretation of the implicitization problem as an eigenproblem using ideas from Rayleigh-Ritz theory in the Calculus of Variations. The algorithm has a symbolic and a numeric mode and reduces the implicitization problem to a computation of the nullspace of a certain matrix. This particularly appealing feature of the algorithm expands dramatically the range of applicability of the algorithm to include parametric families of curves, surfaces and hypersurfaces. The algorithm works for parametric equations specified by very general classes of functions. We implemented the algorithm as part of the standard distribution of Maple.
Several theoretical improvements and their corresponding practical optimizations are still possible with the aim to speed-up considerably the execution of the algorithm: Using modular approaches to avoid intermediate expression swell, analyze the structure of the implicitization matrices to design fast algorithms for the nullspace computation, develop a sparse implicitization theory and identify and extend the available techniques for predicting the degree of the implicit equation in advance. Some other aspects of the algorithm pose intriguing problems of combinatorial nature.
Taking into account the fact that implicitization and parameterization can be seen as dual processes, an important future research direction is the development of a parameterization algorithm based on our implicitization algorithm. Preliminary investigations in this direction indicate some unexpected connections with particular solutions of systems of integral equations. This in turn is very encouraging, because there is a vast literature pertaining to solutions of systems of integral equations.
The Bezout-Cayley-Dixon resultant is a useful and efficient way to solve systems of polynomial equations. This has been known since at least the 1994 paper by Kapur, Saxena, and Yang [KSY]. Their key idea was proven correct in great generality by the 2000 paper of Buse, Elkadi, and Mourrain [BEM]. I will summarize some of the large problems I have solved with it, in which it has routinely bested Groebner basis techniques by several orders of magnitude. I will describe a technique that I use to get around the spurious factor problem.
[BEM] L. Buse, M. Elkadi, and B. Mourrain, Generalized resultants over unirational algebraic varieties. J. Symbolic Comp. 29 (2000), p. 515-526.
[KSY] D. Kapur, T. Saxena, and L. Yang, Algebraic and geometric reasoning using Dixon resultants. In: Proc. of the International Symposium on Symbolic and Algebraic Computation, A.C.M. Press (1994).
Consider the matrix equation X^2AX-AXA=0, where A=[a_{ij}] and X=[x_{ij}] are n by n matrices over the complex numbers with variables x_{ij}. We study the existence of non-trivial solutions to the equation. By applying Groebner Bases techniques, especially elimination theory, we construct explicit solution matrices (X) for the equation. In the 2 by 2 case, we characterize all solutions. For n>2, we give some solutions via the n=2 result.
We survey the state of the art in solving polynomial systems by homotopy methods, both classical and polyhedral. In particular, we give some basic background on the usual linear homotopy methods, and how they are still crucial to the more recent polyhedral homotopy methods. We then conclude with some recent advances, including a current parallel implementation which can find all the necessary binomial start systems for the cyclic-14 problem in less than 5 hours. (This problem, recently considered intractable, involves a system of 14 equations in 14 unknowns whose toric degree is 40116600 and Bezout number is 87178291200.) The computation involved 64 servers, each with dual 824 Mhz Pentium III processors and 640 Mb RAM.
Mixed Volume is usually introduced through certain subdivisions of a certain polytope. (By the time I give this talk, most people in the conference will have heard of this construction.) However, this interpretation of mixed volume is hardly satisfactory. The construction actually obscures many important ideas. For instance, it is really hard to see why and how mixed volume should be a generalization of volume. In this talk, I will cover (or rather hand-wave) some classical material. Then, this basic material will be used to prove Kushnirenko's theorem in a natural way. This will give us some insights on what mixed volume is or what Bernstein's Theorem means. Finally, I will briefly mention some of the applications of this ``classical'' insight to mixed volume. This talk is based on joint work with Maurice Rojas.
Moreno-Socias conjectured in his thesis a simple combinatorial property of the reverse lexicographic initial ideal of an ideal generated by a generic sequence of homogeneous polynomials, of specified degrees. I have shown that this conjecture implies Froberg's long-standing conjecture on the Hilbert series of such ideals. I will discuss what is known about the Moreno-Socias Conjecture, and some special matrices that Austin Parker and I are studying in hopes of proving a new case.
In practice, many polynomial optimization problems have additional algebraic properties that, suitably exploited, allow for much more efficient algorithms. In this talk, we focus on two specific cases in the context of the sum of squares / semidefinite programming framework. The first one is when the input polynomials are sparse, in the sense that they have few nonzero terms, and is analyzed using Newton polytopes techniques based on earlier work by Reznick. The other case happens when the polynomials are invariant under a group of transformations, where results by Gatermann and the speaker can be applied to obtain a significant reduction in the computational cost. We illustrate the results with an example from geometric theorem proving, due to Peretz, where the combination of the techniques make possible a very elegant and efficient solution.
We present a simple, suprisingly fast algorithm for deciding whether a collection of multivariate polynomials with integer coefficients has a complex root. The algorithm is completely different from the usual Groebner basis, homotopy, or resultant techniques, and is instead based on an oracle sampling trick for checking the density of primes p for which the equations have a root mod p. The punchline is that, under a number theoretic assumption, our algorithm is polynomial time if P=NP. Put another way, one gets an alternative approach to proving that P differs from NP: show that Hilbert's Nullstellensatz takes super-polynomial time to solve.
The underlying assumption is a weakening of the Generalized Riemann Hypothesis (GRH) to a statement about the density of zeroes of the underlying Dedekind zeta function. In particular, the results above were previously known (via seminal work of Pascal Koiran) only under the assumption of the full GRH. We also present similar speed-ups for computing the dimension of a complex algebraic set and detecting rational points on certain zero-dimensional algebraic sets.
It is a difficult problem to say anything meaningful about the number of real solutions to a system of equations. Recently, Eremenko and Gabrielov introduced a notion, that of the real degree of a projection map, that can give a non-trivial lower bound on the number of real solutions to some systems of polynomial equations.
In this talk, I will describe this idea of Eremenko and Gabrielov, give some applications, and discuss its limitations. In addition, I will show how this degree may be computed for some projections of some toric varieties.
We will first describe the facilities for computing primary decompositions and related constructions in Macaulay 2. Unfortunately, on most "real-world" research problems, canned algorithms for primary decomposition do not work very well: they often get bogged down and never finish in a reasonable time. In this talk, we describe what to try when this happens to your example. These techniques are useful for any computer algebra system. We will illustrate these techniques with examples from Macaulay 2.
The problem to characterize and compute the lines tangent to 2n-2 given spheres in R^n arises in various applications in computational geometry. Since many algebraic-geometric properties and constructions hereof can be well described in terms of dynamic configurations, polynomial homotopy methods turn out to be particularly suited for analyzing and visualizing this problem.
For the three-dimensional case, we discuss the prototype of a homotopy-based 3D visualization tool and illustrate how it can support the study of real solutions. We then show how these analysis techniques can be generalized in order to solve the real enumerative questions of the corresponding n-dimensional tangent problems.
[1] D. Kotzor and T. Theobald: Homotopy techniques for real-time visualization of geometric tangent problems. Video presentation; to appear on the ACM Symposium on Computational Geometry, Barcelona, 2002.
[2] F. Sottile and T. Theobald: Lines tangent to 2n-2 spheres in R^n; to appear in Trans. Amer. Math. Soc.
Homotopy continuation methods are numerically stable algorithms to approximate all isolated solutions of polynomial systems. These methods provide constructive proofs for Bezout's theorem, are able to exploit sparsity, and provide effective algorithms for a numerical Schubert calculus [1]. A recent development [2] applies homotopies to find representations of all irreducible components of the solution sets, for all dimensions and degrees. For this problem, we employ homotopies in three ways: 1) to compute generic points on every component, for all dimensions; 2) to determine whether a given point belongs to a certain component; 3) to factor solution sets into irreducible components. Applications from mechanism design [3] motivate the development and use of homotopy algorithms.
[1] Jan Verschelde: "Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation". ACM Transactions on Mathematical Software 25(2): 251-276, 1999.
[2] Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler: "Numerical Irreducible Decomposition using PHCpack". To appear in "Mathematics and Visualization" (ed. by M. Joswig and N. Takayama).
[3] Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler: "Advances in Polynomial Continuation for Solving Problems in Kinematics". Accepted by the Mechanisms and Robotics sub-conference of ASME DETC2002 (Design Engineering Technical Conferences).
We compute the Bernstein-Sato polynomial b_Q(s) of a generic central arrangement Q=\prod_{i=1}^k H_i of hyperplanes. We establish a connection between the roots of b_Q(s) and the degrees of the generators for the top cohomology of the corresponding Milnor fiber. This connection holds for all homogeneous polynomials. We also introduce certain subschemes of the arrangement determined by the roots of b_Q(s).