A numerical algorithm for zero counting. III: Randomization and condition
From MaRDI portal
Publication:651058
DOI10.1016/J.AAM.2011.07.001zbMATH Open1245.65189arXiv1007.1597OpenAlexW3101405261WikidataQ57733099 ScholiaQ57733099MaRDI QIDQ651058FDOQ651058
Authors: Felipe Cucker, Teresa Krick, Gregorio Malajovich, Mario Wschebor 
Publication date: 8 December 2011
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Abstract: In a recent paper (Cucker, Krick, Malajovich and Wschebor, A Numerical Algorithm for Zero Counting. I: Complexity and accuracy, J. Compl.,24:582-605, 2008) we analyzed a numerical algorithm for computing the number of real zeros of a polynomial system. The analysis relied on a condition number kappa(f) for the input system f. In this paper, we look at kappa(f) as a random variable derived from imposing a probability measure on the space of polynomial systems and give bounds for both the tail P{kappa(f) > a} and the expected value E(log kappa(f)).
Full work available at URL: https://arxiv.org/abs/1007.1597
Recommendations
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- On a condition number of general random polynomial systems
- A numerical algorithm for zero counting. I: Complexity and accuracy
- High probability analysis of the condition number of sparse polynomial systems
- Smoothed analysis for the condition number of structured real polynomial systems
Cites Work
- Title not available (Why is that?)
- Local operator theory, random matrices and Banach spaces.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Level Sets and Extrema of Random Processes and Fields
- Title not available (Why is that?)
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- On Smale's 17th problem: a probabilistic positive solution
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- On condition numbers and the distance to the nearest ill-posed problem
- 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
- Note on matrices with a very ill-conditioned eigenproblem
- Complexity estimates depending on condition and round-off error
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- Ill-Conditioned Matrices Are Componentwise Near to Singularity
- On the probability distribution of data at points in real complete intersection varieties
- A numerical algorithm for zero counting. I: Complexity and accuracy
- The probability that a slightly perturbed numerical analysis problem is difficult
Cited In (15)
- Real roots of random polynomials: expectation and repulsion
- Smoothed analysis for the condition number of structured real polynomial systems
- Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian
- Grid methods in computational real algebraic (and semialgebraic) geometry
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Rice formula for processes with jumps and applications
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- On the complexity of the Plantinga-Vegter algorithm
- Computing the homology of semialgebraic sets. I: Lax formulas
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- On the condition of the zeros of characteristic polynomials
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- On a condition number of general random polynomial systems
- On the expected number of zeros of nonlinear equations
- Computing the homology of real projective sets
This page was built for publication: A numerical algorithm for zero counting. III: Randomization and condition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651058)
