A numerical algorithm for zero counting. III: Randomization and condition
From MaRDI portal
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)).
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
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- scientific article; zbMATH DE number 1158743 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- A numerical algorithm for zero counting. I: Complexity and accuracy
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- Complexity estimates depending on condition and round-off error
- 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. VI: Geodesics in the condition (number) metric
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Ill-Conditioned Matrices Are Componentwise Near to Singularity
- Level Sets and Extrema of Random Processes and Fields
- Local operator theory, random matrices and Banach spaces.
- Note on matrices with a very ill-conditioned eigenproblem
- On Smale's 17th problem: a probabilistic positive solution
- On condition numbers and the distance to the nearest ill-posed problem
- On the probability distribution of data at points in real complete intersection varieties
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- 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)
