Newton iteration, conditioning and zero counting
For researchers in computational real algebraic geometry, this work provides a new algorithm for real root counting with complexity analysis.
The lectures address the problem of counting real roots of a system of n real polynomials in n variables. They present an inclusion-exclusion algorithm and analyze its complexity using tools for numerical algorithms.
Those lectures revolve around the following problem: given a system of n real polynomials in n variables, count the number of real roots. The first lecture is a course on Newton iteration and alpha-theory. The second describes an inclusion-exclusion algorithm for real polynomials, developed by Felipe Cucker, Teresa Krick, Mario Wschebor and myself. The third lecture introduces tools for complexity analysis of numerical algorithms, and uses those tools to analyze our root-counting algorithm.