Mathematical Sciences: Complexity of Real Computation and Zeros of Polynomial Systems

点击翻译按钮获取中文摘要

Smale The investigator studies algorithms based on Newton's method for finding zeros of a system of polynomials. The focus of the analysis is to obtain bounds on the number of Newton steps required. Such bounds will depend on the number of variables, the degrees of the polynomials, and the desired accuracy. The goal of the project is a complexity theory of nonlinear equation solving. Equation solving is at the heart of much of mathematics and the main theoretical problem associated to its modern theory of computation is its complexity theory. Equation solving, together with its computational aspects, is a main way that mathematics is used by engineering, physics, economics, and many other disciplines.