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)

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

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)