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.

计算代数几何是研究在计算机上处理代数方程组解集的学科。该领域的起源始于 20 世纪 60 年代的 Buchberger 算法，重点关注具有整数系数的多项式方程的精确计算。是从现代计算的角度研究具有实数和复数系数的多项式方程的计算这项研究受到多元多项式的新兴应用的启发。该研究的教育部分包括培训不同学科的本科生、创建学生可参与的研究研讨会以及开发多个本科生和研究生课程。该项目解决了实多项式算法的实际性能与计算代数几何基于最坏情况的复杂性估计之间的巨大差异，研究人员旨在开发实数和复数稀疏多项式系统求解复杂性的平均情况上限。该项目取得的进展将有利于数值数据多项式计算的应用，并为基于数值数据的多项式计算的应用奠定基础。用于实数和复数多项式计算的平均情况复杂性理论。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On the Complexity of the Plantinga–Vegter Algorithm

论 PlantingaâVegter 算法的复杂性

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

Beyond Worst-Case Analysis for Root Isolation Algorithms

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

DOI：
10.1145/3476446.3535475
发表时间：
2022-07
期刊：
International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
Ergür, Alperen;Tonelli;Tsigaridas, Elias
通讯作者：
Tsigaridas, Elias

The rank of sparse random matrices

稀疏随机矩阵的秩

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

Functional norms, condition numbers and numerical algorithms in algebraic geometry

代数几何中的函数范数、条件数和数值算法