CDS&E-MSS: Computational Developments of Power Series Methods to Solve Polynomial Systems

CDS

基本信息

批准号：
1854513
负责人：
Jan Verschelde
金额：
$ 23.6万
依托单位：
University of Illinois at Chicago
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1854513&HistoricalAwards=false
关键词：
CDS&E MSS Computational Developments Power

项目摘要

Polynomial systems occur in many mathematical models. For example, the design of a robot arm requires the solutions of a system of polynomial equations, as those solutions determine the design parameters of the robot arm, for it to reach desired positions. The proposed research project develops algorithms and software to solve polynomial systems more efficiently and accurately. Massively parallel algorithms on graphics processing units (GPUs) will be capable of solving large polynomial systems. A web server at www.phcpack.org will give anyone via the internet access to the developed software, the free and open source package PHCpack and its scripting interface phcpy. The award will provide support graduate student training through research.The proposed research addresses several computational challenges occurring in the exploitation of the sparse structure when solving a polynomial system. The tropical prevariety provides a collection of polyhedral cones of pretropisms, which are candidates leading forms of Puiseux series of positive dimensional solution sets of the polynomial system. As faces of cones may correspond to higher dimensional solution sets, the exploration of the tropical prevariety will proceed by generalized cascade homotopies which move from higher to lower dimensional solutions. The second computational challenge concerns the robustness of numerical algorithms to track solution paths defined by polynomial homotopies. Using rational approximations based on power series developments, singularities near a solution path are detected which allows to reduce the step size to avoid divergence from the solution path. Following the theory of analytic continuation, rational approximations are very effective tools to deduce information about singularities of the solution paths as function of the continuation parameter in the homotopy. The third challenge concerns the integration of pipelining, multithreading, and GPU acceleration into the solver, as needed to solve large problems.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.

多项式系统出现在许多数学模型中。例如，机器人手臂的设计需要多项式方程组的解，因为这些解决定了机器人手臂的设计参数，以使其到达所需位置。拟议的研究项目开发算法和软件来更有效、更准确地求解多项式系统。图形处理单元 (GPU) 上的大规模并行算法将能够求解大型多项式系统。 www.phcpack.org 上的网络服务器将使任何人都可以通过互联网访问所开发的软件、免费开源包 PHCpack 及其脚本接口 phcpy。该奖项将通过研究为研究生培训提供支持。拟议的研究解决了在求解多项式系统时利用稀疏结构时出现的几个计算挑战。热带前向性提供了前向性多面体锥体的集合，它们是多项式系统的正维解集的 Puiseux 级数的候选主导形式。由于锥体的面可能对应于更高维的解集，因此对热带预变性的探索将通过从高维解移动到低维解的广义级联同伦来进行。第二个计算挑战涉及数值算法跟踪多项式同伦定义的解路径的鲁棒性。使用基于幂级数展开的有理近似，可以检测解路径附近的奇点，从而可以减小步长以避免偏离解路径。遵循解析延拓理论，有理逼近是非常有效的工具，可以根据同伦中的延拓参数推导有关解路径奇点的信息。第三个挑战涉及将管道、多线程和 GPU 加速集成到求解器中，以满足解决大型问题的需要。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Numerical Schubert calculus via the Littlewood-Richardson homotopy algorithm

通过 Littlewood-Richardson 同伦算法进行数值舒伯特微积分

DOI：
10.1090/mcom/3579
发表时间：
2021-05
期刊：
Mathematics of Computation
影响因子：
2
作者：
Leykin, Anton;Martín del Campo, Abraham;Sottile, Frank;Vakil, Ravi;Verschelde, Jan
通讯作者：
Verschelde, Jan

Locating the Closest Singularity in a Polynomial Homotopy

定位多项式同伦中最接近的奇点