High probability analysis of the condition number of sparse polynomial systems

DOI10.1016/J.TCS.2004.01.006zbMATH Open1067.65053arXivmath/0212179OpenAlexW2146491975MaRDI QIDQ598221FDOQ598221

Authors: Gregorio Malajovich, J. Maurice Rojas 

Publication date: 6 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

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 {�f mixed volume} form, thus recovering the classical mixed volume when U = (C^*)^n.

Full work available at URL: https://arxiv.org/abs/math/0212179

Recommendations

• Condition Number Analysis for Sparse Polynomial Systems
• The Maximum Likelihood Degree of Sparse Polynomial Systems
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• Condition number based complexity estimate for solving polynomial systems
• On a condition number of general random polynomial systems
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Probabilistic analysis of condition numbers for linear programming
• Quantitative equidistribution for the solutions of systems of sparse polynomial equations
• Sparse Polynomial Approximation of High-Dimensional Functions

zbMATH Keywords

condition number[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=K%EF%BF%BD%EF%BF%BDhler+geometry&go=Go K��hler geometry]mixed volumeNewton polytopesreal rootsrandom polynomial system

Mathematics Subject Classification ID

Random fields (60G60) Numerical computation of solutions to systems of equations (65H10) Real polynomials: location of zeros (26C10)

Cites Work

• Title not available (Why is that?)
• Convexity properties of the moment mapping
• Topology and mechanics. I
• Title not available (Why is that?)
• Hamiltoniens périodiques et images convexes de l'application moment
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How many zeros of a random polynomial are real?
• Convexity and Commuting Hamiltonians
• Title not available (Why is that?)
• Amoebas, Monge-Ampère measures, and triangulations of the Newton polytope
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Moment maps and combinatorial invariants of Hamiltonian \(T^ n\)-spaces
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The number of roots of a system of equations
• Tangent Graeffe iteration
• Complexity of Bezout's theorem. V: Polynomial time
• Complexity of Bezout's theorem. III: Condition number and packing
• Complexity of Bezout's Theorem I: Geometric Aspects
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding mixed cells in the mixed volume computation
• The expected number of real roots of a multihomogeneous system of polynomial equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the geometry of Graeffe iteration
• Angular momentum, convex Polyhedra and Algebraic Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• High probability analysis of the condition number of sparse polynomial systems

Cited In (29)

• Real zeros of mixed random fewnomial systems
• Probabilistic analysis of the Grassmann condition number
• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• On the number of real zeros of random fewnomials
• Expected multivolumes of random amoebas
• Efficient approximation of the solution of certain nonlinear reaction-diffusion equations with small absorption
• Smoothed analysis for the condition number of structured real polynomial systems
• Deformation techniques for sparse systems
• A numerical algorithm for zero counting. III: Randomization and condition
• Statistics of stationary points of random finite polynomial potentials
• On the probability distribution of data at points in real complete intersection varieties
• High probability analysis of the condition number of sparse polynomial systems
• Random systems of polynomial equations. The expected number of roots under smooth analysis
• Polyhedral homotopies in Cox coordinates
• Computing mixed volume and all mixed cells in quermassintegral time
• Average Euler characteristic of random real algebraic varieties
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
• Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
• A polyhedral homotopy algorithm for real zeros
• On the number of minima of a random polynomial
• On the Kostlan-Shub-Smale model for random polynomial systems. Variance of the number of roots
• On the solution of the polynomial systems arising in the discretization of certain ODEs
• Approximation of the solution of certain nonlinear ODEs with linear complexity
• On the expected number of real roots of polynomials and exponential sums
• On a condition number of general random polynomial systems
• On the expected number of zeros of nonlinear equations
• On solving univariate sparse polynomials in logarithmic time
• On the probability distribution of singular varieties of given corank

This page was built for publication: High probability analysis of the condition number of sparse polynomial systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598221)