Newton iteration, conditioning and zero counting

2012/11/09 by Gregorio Malajovich, Malajovich, Gregorio
Computer Science · Mathematics · #Numerical Methods and Algorithms #Mathematical and Theoretical Analysis #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1211.2120

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.

Related

• Counting Polynomial Roots in Isabelle/HOL: A Formal Proof of the Budan-Fourier Theorem
• Certified counting of roots of random univariate polynomials
• On the Efficient Global Dynamics of Newton's Method for Complex Polynomials
• Discovering the roots: Uniform closure results for algebraic classes under factoring
• When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial