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

AF：SMALL：多项式计算的超越最坏情况分析

基本信息

批准号：
2110075
负责人：
Alperen Ergur
金额：
$ 7.94万
依托单位：
University of Texas at San Antonio
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2110075&HistoricalAwards=false
关键词：
AF SMALL Beyond Worst Case

项目摘要

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.

计算代数几何形状是对计算机上代数方程的解决方案集的有效方法的研究。该领域的起源从60年代的布赫伯格算法开始，重点是对具有整数系数的多项式方程的精确计算。这项研究的目的是从现代计算的角度研究具有真实数量系数的多项式方程的计算。这项研究的灵感来自多元多项式（具有实际财务）在工程中的新兴应用，并源于复杂性理论的基本问题。这项研究的教育部分包括培训来自不同学科的本科生，创建可访问的学生的精确研究以及多个本科和研究生课程的发展。该项目解决了算法在实际多项式上的实践表现之间的巨大差异与基于最差的基于最差的复杂性估计计算质量algeational Algebraic geometry。研究者的目的是开发平均案例上限，以在真实和复数上解决稀疏多项式系统的复杂性，在随机网络上基于多种多项式的算法的复杂性的上限，以及基于CONVEX编程方法的平均值下限，以实现代数计算。该项目中取得的进展将使多项式计算具有数值数据的应用，以及对真实和复杂数字的多项式计算的平均案例复杂性理论的发展基础。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子优点和更广泛影响的审查标准来通过评估而被认为是珍贵的支持。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On the Complexity of the Plantinga–Vegter Algorithm

论 PlantingaâVegter 算法的复杂性

DOI：
10.1007/s00454-022-00403-x
发表时间：
2022
期刊：
Discrete & Computational Geometry
影响因子：
0.8
作者：
Cucker, Felipe;Ergür, Alperen A.;Tonelli-Cueto, Josué
通讯作者：
Tonelli-Cueto, Josué

The rank of sparse random matrices

稀疏随机矩阵的秩

DOI：
10.1002/rsa.21085
发表时间：
2022
期刊：
Random Structures & Algorithms
影响因子：
1
作者：
Coja‐Oghlan, Amin;Ergür, Alperen A.;Gao, Pu;Hetterich, Samuel;Rolvien, Maurice
通讯作者：
Rolvien, Maurice

Beyond Worst-Case Analysis for Root Isolation Algorithms

根隔离算法超越最坏情况分析