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

数学科学：实数计算的复杂性和多项式系统的零点

• 批准号: 9424269
• 负责人: Stephen Smale
• 金额: $ 3万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1999-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9424269&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Complexity; Real; Computation

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.

研究人员斯梅尔研究了基于牛顿方法的求多项式系统零点的算法。分析的重点是获得所需牛顿步数的界限。这样的界限将取决于变量的数量、多项式的次数和期望的精度。该项目的目标是一种非线性方程求解的复杂性理论。方程求解是许多数学的核心，与其现代计算理论相关的主要理论问题是其复杂性理论。方程求解，连同它的计算方面，是工程、物理、经济学和许多其他学科使用数学的主要方式。