Mario Wschebor

Felipe Cucker, Teresa Krick, Gregorio Malajovich et al.

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)).

Diego Armentano, Mario Wschebor

We consider random systems of equations over the reals, with $m$ equations and $m$ unknowns $P_i(t)+X_i(t)=0$, $t\in\mathbb{R}^m$, $i=1,...,m$, where the $P_i$'s are non-random polynomials having degrees $d_i$'s (the "signal") and the $X_i$'s (the "noise") are independent real-valued Gaussian centered random polynomial fields defined on $\mathbb{R}^m$, with a probability law satisfying some invariance properties. For each $i$, $P_i$ and $X_i$ have degree $d_i$. The problem is the behavior of the number of roots for large $m$. We prove that under specified conditions on the relation signal over noise, which imply that in a certain sense this relation is neither too large nor too small, it follows that the quotient between the expected value of the number of roots of the perturbed system and the expected value corresponding to the centered system (i.e., $P_i$ identically zero for all $i=1,...,m$), tends to zero geometrically fast as $m$ tends to infinity. In particular, this means that the behavior of this expected value is governed by the noise part.

Felipe Cucker, Teresa Krick, Gregorio Malajovich et al.

We show a Condition Number Theorem for the condition number of zero counting for real polynomial systems. That is, we show that this condition number equals the inverse of the normalized distance to the set of ill-posed systems (i.e., those having multiple real zeros). As a consequence, a smoothed analysis of this condition number follows.