权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Polynomial Homotopy Continuation: Under the Hood

多项式同伦延拓：幕后黑手

基本信息

批准号：
1719968
负责人：
Anton Leykin
金额：
$ 25万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-06-15 至 2021-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1719968&HistoricalAwards=false
关键词：
Polynomial Homotopy Continuation Under Hood

项目摘要

Systems of polynomial equations are ubiquitous in mathematical models in science and engineering. The field of algebraic geometry, which studies solutions to such systems, has the potential to improve techniques for practical numerical investigations of these systems. This research project aims to apply algebraic geometry to advance numerical algorithms for solving systems of polynomial equations. The research includes developing new homotopy continuation methods that exploit the action of the monodromy group, random walk homotopies, and hybrid algorithms for solving sparse systems. The new theoretical framework and algorithms will be implemented in open-source software. Homotopy continuation algorithms are a backbone of modern nonlinear algebra, the art of solving systems of equations that are not necessarily linear. The main strength of these algorithms is in approximate computation, which often is much faster than classical exact techniques and allows tackling problems in high-dimensional spaces. Homotopy continuation methods solve a problem A in three steps: (1) look for a problem B in the same family of problems as A, but with a simpler structure; (2) construct solutions to that simpler problem B; (3) connect A and B with a homotopy, that is, a continuous deformation, and track how solutions of B morph into solutions of A. This project aims to develop a novel framework for basic homotopy continuation routines. One major point is that randomizing numerical algorithms to a greater extent makes them even faster and more robust without a costly increase in computational precision. Another point is that, looking to minimize computational costs, we should invent new hybrid methods intertwining exact and approximate techniques originating in different areas of mathematics. The symbiosis of symbolic, combinatorial, and numerical ideas is the key to the new methods for solving sparse systems. Tools from tropical geometry and numerical algebraic geometry will deliver a generalization of polyhedral homotopy algorithms and lead to a faster polynomial system solver that benefits from a tighter solution count.

在科学和工程的数学模型中，多项式方程组是普遍存在的。研究此类系统的解的代数几何领域具有改进这些系统的实际数值研究的技术的潜力。这项研究项目旨在应用代数几何来改进求解多项式方程组的数值算法。研究包括开发新的同伦延拓方法，利用单调群的作用，随机游走同伦，以及求解稀疏系统的混合算法。新的理论框架和算法将在开源软件中实现。同伦延拓算法是现代非线性代数的支柱，是求解不一定是线性的方程系统的艺术。这些算法的主要优势在于近似计算，它通常比经典的精确技术快得多，并允许在高维空间中处理问题。同伦延拓方法通过三个步骤解决问题A：(1)在与A相同的问题族中寻找一个结构更简单的问题B；(2)构造更简单的问题B的解；(3)用一个同伦，即连续变形来连接A和B，并跟踪B的解是如何变成A的解的。本项目旨在开发一个新的基本同伦延拓例程的框架。主要的一点是，在更大程度上随机化数值算法会使它们更快、更健壮，而不会代价高昂地提高计算精度。另一点是，为了最小化计算成本，我们应该发明新的混合方法，将源自不同数学领域的精确和近似技术相互交织在一起。符号、组合和数值思想的共生是解决稀疏系统的新方法的关键。热带几何和数值代数几何的工具将提供多面体同伦算法的泛化，并导致更快的多项式系统解算器，受益于更紧密的解计数。

项目成果

期刊论文数量（12）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Monodromy Solver: Sequential and Parallel

单向求解器：顺序和并行

DOI：
10.1145/3208976.3209007
发表时间：
2018
期刊：
ISSAC 2018
影响因子：
0
作者：
Bliss, Nathan;Duff, Timothy;Leykin, Anton;Sommars, Jeff
通讯作者：
Sommars, Jeff

Effective Certification of Approximate Solutions to Systems of Equations Involving Analytic Functions

涉及解析函数的方程组近似解的有效证明

DOI：
10.1145/3326229.3326235
发表时间：
2019
期刊：
ISSAC '19: Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
Burr, Michael;Lee, Kisun;Leykin, Anton
通讯作者：
Leykin, Anton

A numerical toolkit for multiprojective varieties

多射影簇数值工具包

DOI：
10.1090/mcom/3566
发表时间：
2021
期刊：
Mathematics of Computation
影响因子：
2
作者：
Hauenstein, Jonathan;Leykin, Anton;Rodriguez, Jose;Sottile, Frank
通讯作者：
Sottile, Frank

Certification for polynomial systems via square subsystems

通过平方子系统认证多项式系统

DOI：
10.1016/j.jsc.2020.07.010
发表时间：
2020
期刊：
Journal of Symbolic Computation
影响因子：
0.7
作者：
Duff, Timothy;Hein, Nickolas;Sottile, Frank
通讯作者：
Sottile, Frank

TRPLP – Trifocal Relative Pose From Lines at Points

DOI：
10.1109/cvpr42600.2020.01209
发表时间：
2020-06
期刊：
2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
影响因子：
0
作者：
R. Fabbri;Timothy Duff;Hongyi Fan;Margaret H. Regan;David da Costa de Pinho;Elias P. Tsigaridas;C. Wam
通讯作者：
R. Fabbri;Timothy Duff;Hongyi Fan;Margaret H. Regan;David da Costa de Pinho;Elias P. Tsigaridas;C. Wam