权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Complexity of operations with Pfaffian and Noetherian functions and effective o-minimality

普法夫函数和诺特函数运算的复杂性以及有效的 o 极小性

基本信息

批准号：
0070666
负责人：
Andrei Gabrielov
金额：
$ 9万
依托单位：
Purdue Research Foundation
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2000
资助国家：
美国
起止时间：
2000-07-01 至 2003-11-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0070666&HistoricalAwards=false
关键词：
Complexity operations Pfaffian Noetherian functions

项目摘要

A. Gabrielov proposes to continue research on the theory of Pfaffian and Noetherian functions (analytic functions satisfying systems of partial differential equations with polynomial coefficients), with applications to quantifier elimination, o-minimality, and computational complexity. The goal of this research is to establish effective upper bounds for the complexity of algebro-geometric operations on Pfaffian functions and the sets defined by expressions with such functions in the real domain. This can be considered as a quantitative, effective version of the o-minimal theory of Pfaffian functions. For Noetherian functions, where global o-minimality fails, the goal is to develop local real and complex analogs of this theory.Modern computer algebra systems allow one to perform on a computer many operations with algebraic equations and inequalities previously considered the domain of abstract algebraic geometry. One of the latests achievements is an algorithm for the resolution of singularities of systems of algebraic equations. The results can be applied to such practical problems as visualisation, robotics, and the coding theory. The complexity of computer codes performing these operations becomes a practically important problem. This complexity usually grows fast with the degree of polynomials. The Pfaffian theory allows one to significantly reduce the computational complexity of operations on "fewnomials" - polynomials of high degree with few non-zero terms. The goal of the proposed research is to combine the Pfaffian theory with the algorithmic resolution of singularities, in order to develop efficient computational procedures for fewnomial systems.

加布里埃洛夫建议继续研究Pfaffian函数和Noether函数(满足多项式系数的偏微分方程组的解析函数)的理论，并将其应用于量词消除、o-最小性和计算复杂性。本研究的目的是建立实域上Pfaffian函数的代数几何运算的复杂性的有效上界，以及由Pfaffian函数的表达式定义的集合。这可以被认为是Pfaffian函数的o-极小理论的一个定量的、有效的版本。对于Noether函数，当全局o-极小值失效时，目标是发展这一理论的局部实数和复数类比。现代计算机代数系统允许人们在计算机上执行许多以前被认为是抽象代数几何领域的代数方程和不等式的运算。最新的成果之一是解代数方程组奇点的算法。研究结果可应用于可视化、机器人学、编码理论等实际问题。执行这些操作的计算机代码的复杂性成为一个实际重要的问题。这种复杂性通常随着多项式次数的增加而快速增长。Pfaffian理论使人们能够显著降低“几项式”的运算复杂性--高次多项式的非零项很少。这项研究的目的是将Pfaffian理论与奇点的算法分解相结合，以开发针对少数几项式系统的高效计算程序。