Math: Algorithms for Parametric (Comprehensive) Groebner Computations

我们将研究求解多元多项式系统的算法，特别关注参数多项式系统，其中不确定项被分成两个不相交的子集--一个由参数组成，另一个由变量组成。在许多应用领域中，这种多项式系统一般用于模拟或近似问题，其中一般问题具有这样的参数，即对于每个参数值，一般问题变得特定。目标是研究参数的不同专门化的解的结构。本研究项目将调查格罗布纳基础计算框架在这一分析中的使用情况。特别地，完备的Groebner基和完备的Groebner系统是优雅的数学对象，它们表示参数多项式系统对于所有可能的参数值的所有解。该项目将探索理论基础，并开发高效和有效的算法来计算全面的Groebner系统和参数多项式系统的全面Groebner基。提出了极小标准综合Groebner基的概念，并探讨了它在研究多项式理想理论和代数几何问题中的意义。研究一种计算最小标准综合Groebner基的有效算法。参数多元多项式系统是建模各种应用领域中许多问题的有力工具。(I)确定给定的多项式方程组是否有公共解，(Ii)导出多项式方程中出现的符号参数的条件，使它们有公共解，以及(Iii)建立公共解的有效表示，这些问题具有基本意义。这些问题出现在工程设计、机器人、逆运动学、图形学、实体建模、CAD-CAM设计、几何构造、药物设计、控制理论以及程序验证和分析等领域。考虑到不同应用领域的许多问题都可以用参数多项式来建模，求解参数多项式系统的快速方法对这些应用是有用的。拟议的研究将导致与综合Groebner计算相关的理论和算法的发展，并调查其在许多应用领域的有效使用，特别是几何设计和建模，以及程序分析和验证。在研究项目期间开发的算法将在包括Magma和Single在内的计算机代数系统中实现，并在不同应用领域出现的各种问题上进行实验。我们将开发和分析启发式算法，以使这些算法及其实现更加高效。

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.