A numerical algorithm for zero counting. III: Randomization and condition

DOI10.1016/j.aam.2011.07.001zbMath1245.65189arXiv1007.1597WikidataQ57733099 ScholiaQ57733099MaRDI QIDQ651058

Felipe Cucker, Mario Wschebor, Teresa Krick, Gregorio Malajovich

Publication date: 8 December 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

average-case analysis; condition numbers; zero counting; Rice formula; finite precision

Mathematics Subject Classification ID

60G60: Random fields

65Y20: Complexity and performance of numerical algorithms

Related Items

Smoothed analysis for the condition number of structured real polynomial systems, Functional norms, condition numbers and numerical algorithms in algebraic geometry, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, Computing the homology of real projective sets, Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions, Grid methods in computational real algebraic (and semialgebraic) geometry, On the complexity of the Plantinga-Vegter algorithm, Computing the homology of semialgebraic sets. I: Lax formulas, Rice formula for processes with jumps and applications, On the expected number of zeros of nonlinear equations, On a condition number of general random polynomial systems, Real roots of random polynomials: expectation and repulsion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Smale's 17th problem: a probabilistic positive solution
• On the probability distribution of data at points in real complete intersection varieties
• A numerical algorithm for zero counting. I: Complexity and accuracy
• 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
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• Complexity of Bezout's theorem. III: Condition number and packing
• A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
• Note on matrices with a very ill-conditioned eigenproblem
• Complexity estimates depending on condition and round-off error
• The probability that a slightly perturbed numerical analysis problem is difficult
• Level Sets and Extrema of Random Processes and Fields
• Complexity of Bezout's Theorem I: Geometric Aspects
• Ill-Conditioned Matrices Are Componentwise Near to Singularity
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions