Newton iteration, conditioning and zero counting

Abstract

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.

arXiv commentLecture notes for the Santaló summer school on Recent Advances in Real Complexity and Computation, Universidad Internacional Menéndez Pelayo, Santander, july 2012