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

点击翻译按钮获取中文摘要

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.