Session II.3 - Real-Number Complexity
Friday, June 16, 15:30 ~ 16:00
On the complexity of sparse polynomial solving.
Gregorio Malajovich
Universidade Federal do Rio de Janeiro, Brazil - This email address is being protected from spambots. You need JavaScript enabled to view it.
Smale's 17-th problem, now solved, asked for an average polynomial time algorithm for finding one root of a random dense polynomial system. The proposed algorithms, as well as all the theoretical framework, rely heavily on the hypotheses of Bézout's Theorem. This theorem states that the number of roots of a `generic' system of $n$ complex polynomials in $n$ variables is the product of the total degrees. `Generic' means Zariski open in the set of systems with a tuple of fixed degrees. A system with vanishing coefficients is not generic. One is induced to homogenize the equations and look for roots in projective space. This suggests a canonical topology and geometry for the space of solutions and a projectively invariant inner product structure in the space of coefficients.
I will report on a program to develop rigorous algorithms for sparse polynomial systems, with reasonable complexity bounds. Sparse polynomials means polynomials that are not constrained to be dense or random. Bernstein's root count in terms of Minkowski's mixed volume is much sharper than Bézout's bound. It assumes polynomial systems with a given support, not necessarily dense. Bernstein's theorem counts the number of roots in a certain toric variety.
Solvoing sparse systems with dense technology is not doable. For instance, a homotopy path between a dense random system and a given sparse sysem is not guaranteed to land on a point of the toric variety. Because the root counts can differ exponentially, that event may be extremely unlikely.
I will bound the cost (number of homotopy steps) of a non-deterministic homotopy between two given sparse systems with the same supports. The cost of this algorithm depends on the supports. For instance, Aleksandrov's mixed area is a quermassintegral that generalizes surface area in the same way that mixed volume generalizes ordinary volume. The facet gap measures, for each 1-cone in the fan and for each support polytope, how close is the supporting hyperplane to the nearest vertex. Once the supports are fixed, the cost can be bounded in terms of two condition numbers of the limiting systems: the renormalized toric condition number and the imbalance of the absolute values of the coefficients.