AF: Small: Collaborative Research: Certification for Semi-Algebraic Sets with Applications
AF:小:协作研究:半代数集及其应用的认证
基本信息
- 批准号:1813340
- 负责人:
- 金额:$ 25万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-10-01 至 2023-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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)
A certified iterative method for isolated singular roots
- DOI:10.1016/j.jsc.2022.08.006
- 发表时间:2022-08
- 期刊:
- 影响因子:0
- 作者:Angelos Mantzaflaris;B. Mourrain;Á. Szántó
- 通讯作者:Angelos Mantzaflaris;B. Mourrain;Á. Szántó
Certified Hermite Matrices from Approximate Roots - Univariate Case
由近似根证明的 Hermite 矩阵 - 单变量情况
- DOI:10.1007/978-3-030-43120-4_1
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Ayyildiz Akoglu, T;Szanto, A.
- 通讯作者:Szanto, A.
Smooth points on semi-algebraic sets
- DOI:10.1016/j.jsc.2022.09.003
- 发表时间:2020-02
- 期刊:
- 影响因子:0.1
- 作者:Katherine Harris;J. Hauenstein;Á. Szántó
- 通讯作者:Katherine Harris;J. Hauenstein;Á. Szántó
Certified Hermite matrices from approximate roots
来自近似根的经认证的 Hermite 矩阵
- DOI:10.1016/j.jsc.2022.12.001
- 发表时间:2023
- 期刊:
- 影响因子:0.7
- 作者:Ayyildiz Akoglu, Tulay;Szanto, Agnes
- 通讯作者:Szanto, Agnes
Punctual Hilbert scheme and certified approximate singularities
- DOI:10.1145/3373207.3404024
- 发表时间:2020-02
- 期刊:
- 影响因子:0
- 作者:Angelos Mantzaflaris;B. Mourrain;Á. Szántó
- 通讯作者:Angelos Mantzaflaris;B. Mourrain;Á. Szántó
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Hoon Hong其他文献
An improvement of the projection operator in cylindrical algebraic decomposition
- DOI:
10.1145/96877.96943 - 发表时间:
1990-07 - 期刊:
- 影响因子:0
- 作者:
Hoon Hong - 通讯作者:
Hoon Hong
A condition for multiplicity structure of univariate polynomials
单变量多项式重数结构的一个条件
- DOI:
10.1016/j.jsc.2020.08.007 - 发表时间:
2020-01 - 期刊:
- 影响因子:0.7
- 作者:
Hoon Hong;Jing Yang - 通讯作者:
Jing Yang
Testing Positiveness of Polynomials
- DOI:
10.1023/a:1005983105493 - 发表时间:
1998-08-01 - 期刊:
- 影响因子:0.800
- 作者:
Hoon Hong;Dalibor Jakuš - 通讯作者:
Dalibor Jakuš
A framework for improving uniformity of parameterizations of curves
- DOI:
10.1007/s11432-013-4924-4 - 发表时间:
2013-10-01 - 期刊:
- 影响因子:7.600
- 作者:
Hoon Hong;DongMing Wang;Jing Yang - 通讯作者:
Jing Yang
Improving angular speed uniformity of rational parameterization using piecewise radical reparameterization
- DOI:
10.1007/s10472-025-09976-8 - 发表时间:
2025-03-27 - 期刊:
- 影响因子:1.000
- 作者:
Hoon Hong;Dongming Wang;Jing Yang - 通讯作者:
Jing Yang
Hoon Hong的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Hoon Hong', 18)}}的其他基金
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: CCF: AF: Medium: Validated Soft Approaches to Parametric ODE Solving
协作研究:CCF:AF:中:经过验证的参数 ODE 求解软方法
- 批准号:
2212461 - 财政年份:2022
- 资助金额:
$ 25万 - 项目类别:
Continuing Grant
AF: Small: Quantifier elimination by group analysis
AF:小:通过组分析消除量词
- 批准号:
1319632 - 财政年份:2013
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
International Conference on Applied Computer Algebra
应用计算机代数国际会议
- 批准号:
0313458 - 财政年份:2003
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Scientific Computing Research Environments for the Mathematical Sciences (SCREMS)
数学科学的科学计算研究环境 (SCREMS)
- 批准号:
9977392 - 财政年份:1999
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
East Coast Computer Algebra Day, April 24, l999, North Carolina State University, Raleigh, North Carolina
东海岸计算机代数日,1999 年 4 月 24 日,北卡罗来纳州立大学,北卡罗来纳州罗利
- 批准号:
9818360 - 财政年份:1998
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402572 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342245 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402571 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant