AF: Small: Comprehensive Groebner, Parametric GCD Computations and Real Geometric Reasoning

AF：小：综合 Groebner、参数 GCD 计算和真实几何推理

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

Mathematical modeling of physical phenomena and cyber-physical systems and prediction from their behavior are hallmarks of scientific investigation. Checking validity of the modeling process is a critical component of this analytical approach. Polynomials are often one of the simplest tools employed in this endeavor. In order to model variations in the size of components and exogenous changes, variables in polynomials are typically classified into parameters and non-parameters. A prime and simple example is that of a quadratic equation a* square(x) + b * x + c, which behaves very differently for different values of its parameters a, b and c. It has equal solutions under certain parameter values, real solutions under other values and complex solutions or no solution at all under different parameter values. Structural properties of models are expressed using parameters since for different parameters, model can behave significantly different. It becomes critical to develop algorithms that can identify different classes of parameter values for which a model behaves significantly different. Such analysis will benefit many diverse applications including robotics, kinematics, modeling, computer vision, drug design based on molecular modeling and chemical relations, genetic pathways, and numerous cyber physical systems integrating control, hardware and software. The project has all of the theoretical, implementation and application components. The fundamental nature of problems investigated in this project and their application in many domain are likely to appeal to a broad set of students with diverse backgrounds especially from under-represented groups, both graduate and undergraduate. The material generated from this project will be integrated into courses on automated reasoning, mathematical modeling and cyber-physical systems that the researchers at the University of New Mexico (UNM) are teaching. The challenges offered and numerous benefits seen for the national laboratories in New Mexico and society at large by engaging in these investigations will attract participation and offer different career opportunities to the UNM students. This project is jointly funded by Algorithmic Foundations in Computing and Communications Foundations and the Established Program to Stimulate Competitive Research (EPSCoR).The project will involve algorithmic development research in solving parametric multivariate polynomial systems symbolically and real geometry reasoning. The main tool used is that of comprehensive Groebner basis computations and their use in many basic primitive used in other symbolic computation algorithms including parametric greatest common division of polynomials. These algorithms will serve as a basis for the development of a pragmatic, incomplete, approximate quantifier elimination approach over the complex numbers and the reals with the goal of producing meaningful and useful output for applications. Unlike Tarski's method and related algorithms based on Collins' Cylindrical Algebraic Decomposition (CAD), comprehensive Groebner basis computations will be used for polynomial equalities. Results about Positivstellensatz for inequalities using the sum of squares approach and real root counting based on quadratic forms will be explored. Techniques for Groebner basis computations will be adapted for polynomial inequalities to develop heuristics to decide non-negativity of polynomials. Since these problems are of very high computational complexity, their relevance in practical applications calls for developing special heuristics specific to application problems. The research team's experience in theorem proving and its application will be exploited to develop a software tool. Heuristics will be explored to make these implementations efficient.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

物理现象和网络物理系统的数学建模以及从它们的行为中进行预测是科学研究的标志。检查建模过程的有效性是这种分析方法的关键组成部分。多项式通常是在这奋进最简单的工具之一。为了模拟组件大小的变化和外部变化，多项式中的变量通常分为参数和非参数。 一个最简单的例子是一个二次方程a* square（x）+ B * x + c，对于参数a、B和c的不同值，它的表现非常不同。它在某些参数值下有相等的解，在其他参数值下有真实的解，在不同参数值下有复解或无解。 模型的结构特性是用参数来表示的，因为对于不同的参数，模型可以表现出显着的不同。开发能够识别模型行为显著不同的不同参数值类别的算法变得至关重要。这种分析将有利于许多不同的应用，包括机器人，运动学，建模，计算机视觉，基于分子建模和化学关系的药物设计，遗传途径，以及集成控制，硬件和软件的众多网络物理系统。该项目具有所有的理论，实施和应用组件。在这个项目中调查的问题的基本性质和他们在许多领域的应用可能会吸引广泛的学生与不同的背景，特别是从代表性不足的群体，研究生和本科生。该项目产生的材料将被整合到新墨西哥州大学（UNM）研究人员正在教授的自动推理、数学建模和网络物理系统课程中。通过参与这些调查，为新墨西哥州和整个社会的国家实验室提供的挑战和众多好处将吸引参与，并为UNM学生提供不同的职业机会。 本计画由计算与通讯基金会中的数学基金会与刺激竞争研究的既定计划（EPSCoR）共同资助，将涉及以符号方式求解参数多元多项式系统与真实的几何推理的演算法发展研究。所使用的主要工具是全面的Groebner基础计算和它们在其他符号计算算法中使用的许多基本原语中的使用，包括多项式的参数最大公除。这些算法将作为一个务实的，不完整的，近似量词消除方法的复数和实数的目标，产生有意义的和有用的输出应用程序的发展的基础。 与塔斯基的方法和基于柯林斯的圆柱代数分解（CAD）的相关算法不同，全面的Groebner基计算将用于多项式等式。本文将探讨利用平方和方法和基于二次型的真实的根计数方法对不等式进行正性估计的结果。Groebner基计算的技术将适用于多项式不等式，以发展数学方法来确定多项式的非负性。由于这些问题是非常高的计算复杂性，其在实际应用中的相关性要求开发特定的应用问题的特殊算法。将利用研究小组在定理证明及其应用方面的经验开发一个软件工具。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。