Math: Algorithms for Parametric (Comprehensive) Groebner Computations

数学：参数（综合）Groebner 计算算法

• 批准号: 1217054
• 负责人: Deepak Kapur
• 金额: $ 29.95万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217054&HistoricalAwards=false
• 关键词: Math; Algorithms; Parametric; Comprehensive; Groebner

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.

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