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

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

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.