AF: SMALL: Beyond Worst-Case Analysis for Computing with Polynomials

计算代数几何是研究在计算机上处理代数方程组解的有效方法。 该领域的起源，从60年代的Buchberger算法开始，专注于整数系数多项式方程的精确计算。本研究的目的是从现代计算的角度研究具有真实的和复数系数的多项式方程的计算。 这项研究的灵感来自多元多项式（真实的系数）在工程中的新兴应用，并在复杂性理论的基本问题有其根源。该研究的教育部分包括培训来自不同学科的本科生，创建学生可访问的研究研讨会，以及开发多个本科生和研究生课程。该项目解决了真实的多项式算法的实际性能与计算代数几何中基于最坏情况的复杂性估计之间的巨大差异。调查的目的是开发平均情况下的上界的复杂性稀疏多项式系统解决了真实的和复数，上界的复杂性的多元多项式为基础的算法随机网络，和平均情况下的下界的凸规划为基础的方法，代数计算。 该项目取得的进展将有利于数值数据多项式计算的应用，并为真实的和复数的多项式计算发展平均情况复杂性理论的基础。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computational algebraic geometry is the study of efficient ways to manipulate solution sets of algebraic equations on a computer. The origins of the field, starting from Buchberger’s algorithm in the 60’s, focused on exact computations on polynomial equations with integer coefficients. The goal of this research is to study computations on polynomial equations with real and complex number coefficients from a modern computational perspective. This research is inspired by the emerging applications of multivariate polynomials (with real coefficients) in engineering, and has its roots in basic questions of complexity theory. The educational component of the research includes training of undergraduate students from different disciplines, creation of a student-accessible research seminar, and development of multiple undergraduate and graduate courses.The project addresses the large discrepancy between practical performance of algorithms on real polynomials and the worst-case-based complexity estimates from computational algebraic geometry. The investigator aims to develop average-case upper bounds for complexity of sparse polynomial system solving over the real and complex numbers, upper bounds for the complexity of multivariate polynomial based algorithms on random networks, and average-case lower bounds for convex programming based approaches to algebraic computations. Progress made in this project will benefit applications of polynomial computations with numerical data, and develop foundations of average-case complexity theory for polynomial computations on real and complex numbers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.