Computing Groebner bases and finding primary decomposition of polynomial ideals are two closely related topics that are fundamental in computational algebraic geometry. Groebner bases provide an essential tool for computation in algebra, especially in solving systems of multivariate polynomials. The primary decomposition theorem was proved by the late chess Master Emanuel Lasker in 1905 for polynomial rings and Emmy Noether in early 1920s for general Noetherian rings. Primary decomposition is a crucial step in computerizing schemes in algebraic geometry, yet it is still a big challenge to provide efficient algorithms for reasonable sized systems of polynomials. The major bottleneck is in computing Groebner bases for systems of polynomials that appear in the process of computing primary decomposition. The main goal of the project is to develop new efficient algorithms for computing Groebner bases and for finding primary decomposition.
Solving polynomial systems is ubiquitous in sciences and engineerings. Its applications include, but not limited to, computer vision, computer-aided designs, coding theory, cryptography, robot kinematics, computational biology, etc. Work in this project would benefit major computer algebra systems and their users in education and industry. It also bears direct applications in reliable and secure communications from Internet commercial to military combats and from cell phones to outer space explorations.
Interllectual Merit. The project studies efficient algorithms for computing Groebner bases and for finding primary decomposition of polynomial ideals, which are two closely related topics that are fundamental in computational algebraic geometry. Groebner bases provides an essential tool for computation in algebra, especially in solving systems of multivariate polynomials. The primary decomposition theorem was proved by the late chess Master Emanuel Lasker in 1905 for polynomial rings and Emmy Noether in early 1920s for general Noetherian rings. Here we highlight two main contributions made during this project. Buchberger introduced in 1965 the first algorithm for computing Groebner bases, and it has been implementedin in most computer algebra systems including Maple, Mathematica, Magma, Sage, Singular, Macaulay 2, CoCoA, etc. There has been extensive effort in finding more efficient algorithms for computing Groebner bases. In 2002, Faugere presented his F5 algorithm that is significantly faster than Buchberger's. However, the F5 algorithm is difficult to understand and proofs of its correctness and finite termination contain significant gaps. In order to remedy this problem, several groups of researchers made extensive effort trying to modify the F5 algorithm. The major contribution of this project is the discovery of a new framework for computing Groebner bases for ideals and the related syzygy modules, in a joint work with Mingsheng Wang from Chinese Academy of Sciences and Frank Volny, a PhD student of the PI's. This framework provides a solid theoretical fundation for easy undertanding of signature-based algorithms proposed in the lieterature from 2002 up to 2014, and enables deeper understanding of designing efficient algorithms for computing Groebner bases. Another major contribution is in factoring sparse polynomials, which is a crucial step in computing primary decomposion of polynomial ideals. The last decade witnessed dramatic progress in factoring multivariate polinomials in dens input form (including the PI's PDE method based on closed differential 1-forms). For sparse polynomials (in terms of straightline programs), however, the story is completely different. Kaltofen and Trager (1990) gave an algorithm (blackbox approach) for finding factors of a sparse polynomial, but their algorithm is not practica. In a joint work with Trevisan Vilmar and Luiz Emilio Allem, we developed a new algorithm that is practical for sparse polynomials represented as straightline programs. Note, when expanded, these polynomials can not be stored in any computer, since they may have so many terms that can out number all the atoms in the universe (hence not enough storage in the world even if each atom can store one term). Broader Impact. Solving polynomial systems is ubiquitous in sciences and engineerings. Its applications include, but not limited to, computer vision, computer-aided designs, coding theory, cryptography, robot kinematics, computational biology, etc. Work in this project would benefit major computer algebra systems and their users in education and industry. It also bears direct applications in reliable and secure communications from Internet commercial to military combats and from cell phones to outer space explorations.
