High probability analysis of the condition number of sparse polynomial systems

DOI10.1016/J.TCS.2004.01.006MaRDI QIDQ598221zbMATH OpenOpenAlexFDO

Authors Gregorio Malajovich, J. Maurice Rojas

Publication date 6 August 2004

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

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

zbMATH Keywords

condition numbermixed volumeNewton polytopesreal rootsrandom polynomial systemKähler geometry

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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
• Efficient approximation of the solution of certain nonlinear reaction-diffusion equations with small absorption
• Expected multivolumes of random amoebas
• 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
• On the number of minima of a random polynomial
• A polyhedral homotopy algorithm for real zeros
• 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)