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.
