Math: Algorithms for Parametric (Comprehensive) Groebner Computations

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

Algorithms for solving multivariate polynomial systems will be investigated with a particular focus on parametric polynomial systems in which indeterminates are classified into two disjoint subsets-- one consisting of parameters and other consisting of variables. Such polynomial systems are used to model or approximate problems generically in many application domains, where a generic problem has parameters such that for every parameter value, the generic problem becomes specific. The objective is to study the structure of solutions for different specializations of parameters. This research project will investigate the use of the framework of Groebner basis computations for this analysis. Particularly, comprehensive Groebner bases and comprehensive Groebner systems are elegant mathematical objects which represent all the solutions of a parametric polynomial system for all possible parameter values. The project will explore theoretical foundations as well as develop efficient and effective algorithms for computing comprehensive Groebner systems and comprehensive Groebner bases for parametric polynomial systems. The concept of a minimal canonical comprehensive Groebner basis will be developed and its significance will be explored for studying problems in polynomial ideal theory and algebraic geometry. An efficient algorithm to compute a minimal canonical comprehensive Groebner basis will be investigated. Parametric multivariate polynomial systems are a powerful tool for modeling many problems in various application domains. The problems of (i) determining whether a given polynomial equation system has a common solution, (ii) deriving conditions on symbolic parameters appearing in polynomial equations such that they have a common solution, and (iii) developing an efficient representation of common solutions are of fundamental significance. These problems arise in diverse applications, including engineering design, robotics, inverse kinematics, graphics, solid modeling, CAD-CAM design, geometric construction, drug-design, control theory, and program verification and analysis. Given that many problems in various application domains can be generically modeled using parametric polynomials, fast methods for solving parametric polynomial systems are useful for those applications. The proposed research will lead to the development of theory and algorithms related to comprehensive Groebner computations and investigation of their effective use in many application domains, with a particular focus on geometric design and modeling, as well as program analysis and verification. The algorithms developed during the research project will be implemented in computer algebra systems including Magma and Singular, and experimented with on a variety of problems arising from different application domains. Heuristics will be developed and analyzed to make these algorithms and their implementations efficient.