AF: Algorithms and software for a new polyhedral polynomial system solver

AF：新型多面体多项式系统求解器的算法和软件

• 批准号: 1115777
• 负责人: Jan Verschelde
• 金额: $ 30万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-06-15 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115777&HistoricalAwards=false
• 关键词: AF; Algorithms; software; new; polyhedral

Polyhedral methods to solve polynomial systems exploit the sparsity structure and give rise to hybrid symbolic-numeric algorithms for the computation of Puiseux series expansions of the solutions. The leading powers of the series are tropisms and are defined by the exact Newton polytopes of the system, while the coefficients of the series are solutions of initial form systems which may have coefficients of limited accuracy. The new algorithms will be implemented in the free open source software system PHCpack, with interfaces to computer algebra systems such as Macaulay 2 and Sage (linking the PHCpack library as a Python module). As almost all modern computers have multiple cores enabling to compute in parallel, we design our algorithms for speedup and quality, using the multiple cores to compensate for the cost of multiprecision arithmetic.Solving polynomial systems is a fundamental problem in mathematics with applications to various fields of science and engineering. Solvers that exploit the sparse structure provide better solutions faster. Algorithms and software produced by the proposed research will be disseminated through the users and developers community of Macaulay 2, a computer algebra system for research and teaching in algebraic geometry and commutative algebra. Implementations on parallel computers will enable the efficient solution of large computational problems.

求解多项式系统的多面体方法利用了稀疏结构，产生了计算解的Puiseux级数展开的符号-数值混合算法。级数的主次方是向度，由系统的精确牛顿多面体定义，而级数的系数是可能具有有限精度系数的初始形式系统的解。新算法将在免费开源软件系统PHCpack中实现，该系统具有与Macaulay 2和Sage等计算机代数系统的接口(将PHCpack库链接为一个Python模块)。由于几乎所有的现代计算机都有多核并行计算，我们设计了算法的加速比和质量，用多核来补偿多精度运算的成本。多项式系统的求解是数学中的一个基本问题，应用于科学和工程的各个领域。利用稀疏结构的解算器更快地提供更好的解。拟议研究产生的算法和软件将通过Macaulay 2的用户和开发人员社区传播，Macaulay 2是一个计算机代数系统，用于代数几何和交换代数的研究和教学。在并行计算机上的实现将使大型计算问题的有效解决成为可能。