AF: Small: Collaborative Research: Certification for Semi-Algebraic Sets with Applications

AF：小：协作研究：半代数集及其应用的认证

基本信息

批准号：
1813340
负责人：
Hoon Hong
金额：
$ 25万
依托单位：
North Carolina State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813340&HistoricalAwards=false
关键词：
AF Small Collaborative Research Certification

项目摘要

Traditionally, computers can very quickly calculate with numbers that have a limited number of digits to get answers that are accurate to a certain precision, or they can much more slowly manipulate formulas and symbols to get exact answers. Recently, a new class of algorithms, called numerical path following algorithms, have been successfully applied to approximate solutions for problems in algebraic geometry, combinatorics, and optimization that were once thought to be purely symbolic in nature. The results of such numerical computations are typically not certified, as they are generated using heuristic methods that relax non-continuous properties of the input into continuous ones. The aim of this research project is to give certification techniques for these non-continuous problems and demonstrate that certificates can be computed with not too much extra work given numerical data. An essential part and motivation for this research is a variety of application areas in other fields such as efficiently handling singularities in reliable geometric computation, certification of optima for semidefinite programs, proving existence of multistability in chemical reaction networks, and exceptional motion in mechanism design. By investigating the practical limits of certifiable methods, this project aims to help specialists decide when they can apply certification methods for their purposes. Moreover, by developing new methods that reduce the gap between certified and non-certified versions, researchers will have the guarantee of certified methods in more of their computations. Integration of education and research is essential to the success of this proposal with this project supportingthe inclusion of graduate and undergraduate students in the research team.The focus of this research is to certify and enhance the handling of polynomial equations and inequalities with exact coefficients which have degenerate solutions known only approximately. The difficulty is that, in many cases, the roots of the exact system behave discontinuously under perturbations of the coefficients. Hence, in these non-continuous cases, traditional numerical certification methods, such as interval arithmetic or alpha-theory, cannot work alone. The study of these degenerate cases is the main topic of this project with the fundamental idea to combine numerical certification techniques with symbolic computations. This project will use insights gained from numerical data to drastically improve the complexity of the computation of exact, symbolic objects, and in turn, use insights from symbolic computation to turn an ill-posed problem into a well-posed one. The hybrid symbolic-numeric approach, using early termination upon success, aims to reduce the complexity in comparison with purely symbolic methods. New techniques for regularizing/deflating singular roots will simplify computations related to singularities and improve applications including the visualization of singular curves lying on a real surface. Additionally, this project will improve the complexity of certification routines by exploiting symmetry.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.

传统上，计算机可以非常快速地使用有限位数的数字进行计算，以获得精确到一定精度的答案，或者它们可以更慢地操作公式和符号以获得准确的答案。最近，一类新的算法，称为数值路径跟踪算法，已成功应用于代数几何、组合学和优化问题的近似解决方案，这些问题曾经被认为本质上是纯粹的符号问题。此类数值计算的结果通常未经认证，因为它们是使用启发式方法生成的，该方法将输入的非连续属性放宽为连续属性。该研究项目的目的是为这些非连续问题提供认证技术，并证明在给定数值数据的情况下无需太多额外工作即可计算出证书。这项研究的一个重要部分和动机是在其他领域的各种应用领域，例如有效处理可靠几何计算中的奇点、半定程序的最优证明、证明化学反应网络中多稳定性的存在以及机构设计中的异常运动。通过调查可认证方法的实际限制，该项目旨在帮助专家决定何时可以将认证方法应用于其目的。此外，通过开发新的方法来缩小认证版本和非认证版本之间的差距，研究人员将在更多的计算中得到认证方法的保证。教育和研究的整合对于该提案的成功至关重要，该项目支持将研究生和本科生纳入研究团队。这项研究的重点是验证和增强对多项式方程和不等式的处理，这些方程具有精确的系数简并解仅近似已知。困难在于，在许多情况下，精确系统的根在系数扰动下表现得不连续。因此，在这些非连续情况下，传统的数值证明方法（例如区间算术或阿尔法理论）无法单独发挥作用。对这些退化案例的研究是该项目的主要主题，其基本思想是将数值证明技术与符号计算相结合。该项目将利用从数值数据中获得的见解来大幅提高精确符号对象计算的复杂性，进而利用符号计算中的见解将不适定问题转变为适定问题。混合符号-数字方法采用成功后提前终止的方法，旨在与纯符号方法相比降低复杂性。正则化/缩小奇异根的新技术将简化与奇异性相关的计算并改进应用程序，包括真实表面上奇异曲线的可视化。此外，该项目将通过利用对称性来提高认证程序的复杂性。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Certified Hermite matrices from approximate roots

来自近似根的经认证的 Hermite 矩阵

DOI：
10.1016/j.jsc.2022.12.001
发表时间：
2023-07
期刊：
Journal of Symbolic Computation
影响因子：
0.7
作者：
Ayyildiz Akoglu, Tulay;Szanto, Agnes
通讯作者：
Szanto, Agnes

Certified Hermite Matrices from Approximate Roots - Univariate Case

由近似根证明的 Hermite 矩阵 - 单变量情况

DOI：
10.1007/978-3-030-43120-4_1
发表时间：
2020-03
期刊：
volume 11989
影响因子：
0
作者：
Ayyildiz Akoglu, T;Szanto, A.
通讯作者：
Szanto, A.

Smooth points on semi-algebraic sets

半代数集上的平滑点

DOI：
10.1145/3457341.3457347
发表时间：
2020-09
期刊：
ACM Communications in Computer Algebra
影响因子：
0.1
作者：
Harris, Katherine;Hauenstein, Jonathan D.;Szanto, Agnes
通讯作者：
Szanto, Agnes

Subresultants of (x−α) and (x−β) , Jacobi polynomials and complexity

(x-α) 和 (x-β) 的子结果、雅可比多项式和复杂性

DOI：
10.1016/j.jsc.2019.10.003
发表时间：
2020-11
期刊：
Journal of Symbolic Computation
影响因子：
0.7
作者：
Bostan, A.;Krick, T.;Szanto, A.;Valdettaro, M.
通讯作者：
Valdettaro, M.

Punctual Hilbert scheme and certified approximate singularities

DOI：
10.1145/3373207.3404024
发表时间：
2020-02-14
期刊：
Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
Angelos Mantzaflaris;B. Mourrain;Á. Szántó
通讯作者：
Á. Szántó