High Probability Analysis of the Condition Number of Sparse Polynomial Systems

Abstract

Let F:=(f_1,...,f_n) be a random polynomial system with fixed n-tuple of supports. Our main result is an upper bound on the probability that the condition number of f in a region U is larger than 1/epsilon. The bound depends on an integral of a differential form on a toric manifold and admits a simple explicit upper bound when the Newton polytopes (and underlying covariances) are all identical. We also consider polynomials with real coefficients and give bounds for the expected number of real roots and (restricted) condition number. Using a Kahler geometric framework throughout, we also express the expected number of roots of f inside a region U as the integral over U of a certain {\bf mixed volume} form, thus recovering the classical mixed volume when U = (C^*)^n.

29 pages, no figures. Extensive revision and streamlining of math.NA/0012104. In particular, new theorem with explicit high probability estimate of the condition number of a random sparse polynomial system (Theorem 1) has been added

References in corpus (5)

• Amoebas of algebraic varieties
• Tangent Graeffe Iteration
• On the Geometry of Graeffe Iteration
• Random Sparse Polynomial Systems
• Successive minima of projective toric varieties

Cited by in corpus (18)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• Turning intractable counting into sampling: computing the configurational entropy of three-dimensional jammed packings
• Zero distribution of random sparse polynomials
• Computing mixed volume and all mixed cells in quermassintegral time
• A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis
• On the number of minima of a random polynomial
• Random systems of polynomial equations. The expected number of roots under smooth analysis
• On the Number of Real Zeros of Random Fewnomials
• When you can't count, sample! Computable entropies beyond equilibrium from basin volumes
• On the expected number of zeros of nonlinear equations
• Statistics of Stationary Points of Random Finite Polynomial Potentials
• Complexity of Sparse Polynomial Solving 2: Renormalization
• A Polyhedral Homotopy Algorithm For Real Zeros
• Expected Multivolumes of Random Amoebas
• On the expected number of real roots of polynomials and exponential sums
• On Solving Fewnomials Over Intervals in Fewnomial Time
• A review of some recent results on random polynomials over R and over C
• Efficient approximation of the solution of certain nonlinear reaction--diffusion equation I: the case of small absorption