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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1115777
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2011-06-15
Budget End
2014-05-31
Support Year
Fiscal Year
2011
Total Cost
$300,000
Indirect Cost
Name
University of Illinois at Chicago
Department
Type
DUNS #
City
Chicago
State
IL
Country
United States
Zip Code
60612