Groebner 基计算的新理论和快速算法研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11171323
项目类别：
面上项目
资助金额：
36.0万
负责人：
王明生
依托单位：
中国科学院信息工程研究所
学科分类：
A0410.算法复杂性与近似算法
结题年份：
2015
批准年份：
2011
项目状态：
已结题
起止时间：
2012-01-01 至2015-12-31

项目参与者：
李永强；邹静；余玉银；吴生宝；钟霄；矫琳；
关键词：
Groebner 基快速算法多项式系统符号计算

项目摘要

项目主要目的是研究计算Groebner基的新理论和快速算法。 Groebner 基的快速计算是符号求解多项式系统的本质步骤之一，在许多科学和工程问题中有重要的应用，是计算代数的挑战性问题之一。本项目建立在申请人已有的计算Groebner基的前期研究工作基础之上，进一步系统地研究计算Groebner基的新理论和新的算法框架。特别是研究我们提出的强Groebner基的各种刻画以及布尔函数环上快速计算Groebner基的算法；研究我们提出的算法的线性代数化以及如何推广到项序为局部和混合项序时所对应的计算方法。力争在项目周期内，发展出快速计算Groebner基的全新理论和算法标准，为它在科学和工程实际问题中的应用提供算法支持。

结项摘要

Groebner基的快速计算的理论与算法是研究如何从多变量多项式理想的一组生成元中快速计算出一个Groebner基。传统的Buchberger算法由于多项式除法要约化到零，已经不适用于快速的计算。法国Faugere提出了基于签名的算法，缺点是签名在实际计算中无法验证，并且没有给出算法的正确性和终止性证明。由于不仅在计算代数几何学科本身，而且在大量的实际应用的领域如密码学，离散优化，控制系统等许多领域都需要求解多元多项式系统，因此快速计算较大规模的多项式系统的Groebner基是具有理论和实际应用价值的重要研究。本项目的主要研究的目的是给出一个快速计算Groebner基的全新算法并完整地给出其正确性和终止性证明。我们在该项目的实施中主要完成下面的两方面的工作。（1）完全给出了快速计算Groebner基的新理论和新算法；主要体现在给出了一个新的计算Groebner基的全新框架；给出了在实际计算时容易计算的签名；提出了全新的强Groebner基的概念，并给出了两个强Groebner基的等价刻画；给出了一个基于强Groebner基概念的计算多项式理想的新算法；这些新的准则为我们计算Groebner基提供了新的基础。（2）在多项式矩阵方面，扩展了Youla的MLP引理，并应用它证明了多变多形式矩阵中一个重要结果；利用发展的关于多变多项式矩阵分解的一般结果，我们对两个变量的多项式矩阵的一般分解结果给出了全新的证明。