论文部分内容阅读
本文主要研究代数、微分多项式系统的零点分解算法.将代数或微分多项式系统的零点集合分解为由三角列表示的纯维代数簇或微分代数簇是符号计算的一个核心算法.在本文中,我们从不同的思路出发,给出了两种类型的零点分解算法,并且这两类算法具有初等的计算复杂度. 首先,我们利用三角列方法给出代数、微分多项式系统的正则分解算法.具体的,对于一个代数多项式系统h1,…,hk∈K[x1,…,xn],我们将给出一个算法使得Zero(h1,…,hk)=N(U)q=1 Zero(sat(Aq)),其中Aq均为正则三角列.这一算法的计算复杂度是关于kn和dncn+2的多项式,其中d满足deg(hi)<d(1≤i≤k),c是一个常数. 对于常微分多项式系统h1,…,hk∈K{x1,…,xn},我们给出一个算法使得Zero(h1,…,hk)=N(U)q=1 Zero(sat(Aq)),其中Aq均为饱和三角列.这一算法的计算复杂度是关于k2n R dc2nRRn的多项式,其中deg(hi)<d,ord(hi)<R对任意1≤i≤k成立,c是一个常数.这是首个具有初等的计算复杂度的微分多项式系统的三角分解算法. 其次,我们利用微分周形式的性质给出齐阶微分根理想的极小素分解算法.我们首先将微分周形式的定义由微分素理想推广到齐阶微分根理想,然后通过确定该微分周形式的阶数上界和次数上界给出一个计算齐阶微分根理想的周形式的算法.根据齐阶微分根理想的周形式的性质,我们通过对其进行因式分解即可得到齐阶微分根理想的一个极小素分解.