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基础计算及其在其他符号计算算法中使用的许多基本原始词中的用途，包括参数最大的多项式分区。这些算法将作为开发综合数和真实词的实用，不完整的近似量词消除方法的基础，目的是为应用程序产生有意义且有用的输出。 与Tarski的方法和基于Collins的圆柱代数分解（CAD）的相关算法不同，全面的Groebner基础计算将用于多项式相等性。将探索基于正方形方法和基于二次形式的真实根计数的总和，以实现阳性的结果。 Groebner基础计算的技术将适用于多项式不平等，以开发启发式方法以决定多项式的非负性。由于这些问题具有很高的计算复杂性，因此它们在实际应用中的相关性要求开发针对应用程序问题的特殊启发式方法。研究团队在定理证明及其应用程序中的经验将被利用以开发软件工具。将探索启发式方法以使这些实施有效。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来评估值得支持的。