A Numerical Algorithm for Zero Counting

Together with Mario Wschebor, Felipe Cucker and Gregorio Malajovich, we produce and analyze a numerical (iterative) algorithm for computing the exact number of real projective zeros of a system of $n$ real homogeneous polynomial equations in $n + 1$ variables. We first show that the number of iterations, and the cost of each iteration, depends on a condition number of the system, in addition to other usual parameters. The algorithm can be implemented with finite precision as long as the round-off unit satisfies some bound depending on the same parameters. Then we show that the condition number that we introduced satisfies an Eckard-Young theorem, as it represents the inverse of the distance of the input system to the ill-posed systems. We derive from this smoothed analysis bounds for it, applying general results obtained by Bürgisser, Cucker and Lotz. Finally, we use specific probability techniques as a Rice theorem to obtain more precise bounds for the tail and the expected value of the condition number, considered as a random variable when imposing a probability measure on the space of polynomial systems.

Joint work with Felipe Cucker (City University of Hong Kong), Gregorio Malajovich (Universidade Federal do Rio de Janeiro) and Mario Wschebor (Universidad de la República del Uruguay).