Certification Algorithms for Polynomial System Solving

多项式系统求解的认证算法

基本信息

  • 批准号:
    1913119
  • 负责人:
  • 金额:
    $ 7.24万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2019
  • 资助国家:
    美国
  • 起止时间:
    2019-08-01 至 2022-07-31
  • 项目状态:
    已结题

项目摘要

Certified algorithms are computations that are guaranteed to never produce a wrong answer when implemented on a real-world computer. These algorithms are important in any setting where the correctness of a computation is critical and errors cannot be tolerated. Such algorithms have potential applications in many fields, including optimization, automation, and graphics. For example, with self-driving cars, it is vital that the decision-making algorithms do not make errors. For instance, if a non-certified algorithm were to miss a small, but important detail, a car might not fit through a gap or cause an accident. As this type of automation becomes more common, the need for corresponding certified computation will increase. The work in this particular project involves the design, development, and implementation of efficient certified methods for finding common solutions to systems of polynomials. The development of the algorithms described in this project fills a current gap in the field of numerical algebraic geometry since previous approaches are either non-certified, i.e., may make mistakes in some cases, or impractical certified methods, i.e., take too long to produce an answer in practical situations. The work in this project is intended to solve these problems, i.e., to be practical and certified. For many computations, algorithms can only produce an approximation to the true answer. Certified algorithms not only produce a final result from a computation, but they also provide estimates on the error between the final answer and the true answer. Developing certified algorithms is a (new) challenge for computational mathematics and computer science. A certified algorithm must, first, be proved to be correct when assuming that a computer can represent all real numbers. Second, the correctness of the algorithm must be justified when the allowed numbers are approximated by the much smaller set of numbers that can be represented on a computer. Therefore, two of the main challenges in certified methods can be summarized as (1) Since many problems involve discretizing a continuous variable, the theory must be developed to ensure that the choice of discretization does not miss any interesting behaviors between discrete steps and (2) Since not all real numbers can be represented on a computer, all tests and computations must be developed to work with approximations, but still produce meaningful data about the underlying real number. The project involves the design, implementation, and development of an efficient and certified homotopy continuation algorithm in dimensions greater than one. The work generalizes the preliminary exploration and implementation developed by the PI in the univariate case. This prototype is very efficient because of its use of new subroutines, based on interval methods, which have more flexibility than previous approaches.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.
认证算法是保证在真实世界的计算机上实现时永远不会产生错误答案的计算。这些算法在任何计算正确性至关重要且不能容忍错误的情况下都很重要。这种算法在许多领域都有潜在的应用,包括优化、自动化和图形。例如,对于自动驾驶汽车,至关重要的是决策算法不会出错。例如,如果未经认证的算法错过了一个小而重要的细节,汽车可能无法通过间隙或导致事故。随着这种类型的自动化变得越来越普遍,对相应的认证计算的需求将会增加。这个特殊项目的工作包括设计、开发和实现有效的认证方法,以找到多项式系统的共同解决方案。本项目中描述的算法的发展填补了数值代数几何领域目前的空白,因为以前的方法要么是未经认证的,即在某些情况下可能会出错,要么是不切实际的认证方法,即在实际情况下需要太长时间才能产生答案。本项目的工作就是要解决这些问题,也就是说,要切实可行,要经过认证。对于许多计算,算法只能产生真实答案的近似值。经过认证的算法不仅从计算中产生最终结果,而且还提供对最终答案与真实答案之间误差的估计。开发认证算法是计算数学和计算机科学的一个(新的)挑战。首先,当假设计算机可以表示所有实数时,必须证明认证算法是正确的。其次,当允许的数字与计算机上可以表示的小得多的数字集近似时,必须证明算法的正确性。因此,证明方法中的两个主要挑战可以概括为:(1)由于许多问题涉及离散化连续变量,因此必须发展理论以确保离散化的选择不会错过离散步骤之间的任何有趣行为;(2)由于并非所有实数都可以在计算机上表示,因此必须开发所有测试和计算以近似工作,但仍然产生有关潜在实数的有意义的数据。该项目涉及设计、实现和开发维度大于1的高效且经过认证的同伦延拓算法。该工作推广了PI在单变量情况下的初步探索和实施。这个原型非常高效,因为它使用了基于区间方法的新子程序,比以前的方法具有更大的灵活性。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
The complexity of subdivision for diameter-distance tests
直径-距离测试细分的复杂性
  • DOI:
    10.1016/j.jsc.2019.06.004
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0.7
  • 作者:
    Burr, Michael;Gao, Shuhong;Tsigaridas, Elias
  • 通讯作者:
    Tsigaridas, Elias
Inflation of Poorly Conditioned Zeros of Systems of Analytic Functions
  • DOI:
    10.1007/s40598-021-00177-9
  • 发表时间:
    2020-09
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Michael A. Burr;A. Leykin
  • 通讯作者:
    Michael A. Burr;A. Leykin
Computability at zero temperature
零温下的可计算性
  • DOI:
    10.1088/1361-6544/ab9c71
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    1.7
  • 作者:
    Burr, Michael;Wolf, Christian
  • 通讯作者:
    Wolf, Christian
On the computability of rotation sets and their entropies
关于旋转集及其熵的可计算性
  • DOI:
    10.1017/etds.2018.45
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0.9
  • 作者:
    BURR, MICHAEL A.;SCHMOLL, MARTIN;WOLF, CHRISTIAN
  • 通讯作者:
    WOLF, CHRISTIAN
{{ 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 }}

Michael Burr其他文献

Subalgebra and Khovanskii bases equivalence
子代数和 Khovanskii 基等价
  • DOI:
    10.48550/arxiv.2402.06057
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Colin Alstad;Michael Burr;Oliver Clarke;Timothy Duff
  • 通讯作者:
    Timothy Duff
Computability in Dynamical Systems
动力系统中的可计算性
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Michael Burr;Christian Wolf
  • 通讯作者:
    Christian Wolf
Childhood epidemiology of anaphylaxis and epinephrine prescriptions in Wales: 1994–1999
  • DOI:
    10.1016/s0091-6749(02)81323-9
  • 发表时间:
    2002-01-01
  • 期刊:
  • 影响因子:
  • 作者:
    Satyapal Rangaraj;David Tuthill;Michael Burr;Mazin Alfaham
  • 通讯作者:
    Mazin Alfaham

Michael Burr的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Michael Burr', 18)}}的其他基金

AF: Small: Subdivision Methods: Correctness and Complexity
AF:小:细分方法:正确性和复杂性
  • 批准号:
    1527193
  • 财政年份:
    2015
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Standard Grant

相似海外基金

CNS Core: Small: Schedulability Analysis of Safety-Critical Real-Time Systems: Beyond Pseudo-polynomial Time Algorithms
CNS 核心:小型:安全关键实时系统的可调度性分析:超越伪多项式时间算法
  • 批准号:
    2141256
  • 财政年份:
    2022
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Standard Grant
New Polynomial GCD and Factorization Algorithms and Software for Maple
Maple 的新多项式 GCD 和因式分解算法和软件
  • 批准号:
    576162-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Alliance Grants
Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications
合作研究:AF:媒介:多项式优化:算法、证书和应用
  • 批准号:
    2211972
  • 财政年份:
    2022
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications
合作研究:AF:媒介:多项式优化:算法、证书和应用
  • 批准号:
    2211971
  • 财政年份:
    2022
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Continuing Grant
Symbolic-numeric algorithms and applications for systems of differential polynomial equations and inequalities
微分多项式方程组和不等式组的符号数值算法和应用
  • 批准号:
    RGPIN-2016-06458
  • 财政年份:
    2021
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Discovery Grants Program - Individual
Symbolic-numeric algorithms and applications for systems of differential polynomial equations and inequalities
微分多项式方程组和不等式组的符号数值算法和应用
  • 批准号:
    RGPIN-2016-06458
  • 财政年份:
    2020
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Discovery Grants Program - Individual
Symbolic-numeric algorithms and applications for systems of differential polynomial equations and inequalities
微分多项式方程组和不等式组的符号数值算法和应用
  • 批准号:
    RGPIN-2016-06458
  • 财政年份:
    2019
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Discovery Grants Program - Individual
Polynomial-time Algorithms for Analysis and Control of Epidemic Spreading Processes
流行病传播过程分析与控制的多项式时间算法
  • 批准号:
    18K13777
  • 财政年份:
    2018
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
CRII: AF: Strongly Polynomial Algorithms for Market Equilibria with Applications to Network Flows and Nash Social Welfare
CRII:AF:市场均衡的强多项式算法及其在网络流量和纳什社会福利中的应用
  • 批准号:
    1755619
  • 财政年份:
    2018
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Standard Grant
Symbolic-numeric algorithms and applications for systems of differential polynomial equations and inequalities
微分多项式方程组和不等式组的符号数值算法和应用
  • 批准号:
    RGPIN-2016-06458
  • 财政年份:
    2018
  • 资助金额:
    $ 7.24万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了