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

DOI10.1016/j.aam.2011.07.001zbMath1245.65189arXiv1007.1597OpenAlexW3101405261WikidataQ57733099 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 analysiscondition numberszero countingRice formulafinite precision

Mathematics Subject Classification ID

Random fields (60G60) Complexity and performance of numerical algorithms (65Y20)

Related Items

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

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