基于稀疏插值的多项式代数算法及其应用

来源 :华东师范大学 | 被引量 : 3次 | 上传用户:kelly2457
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
多项式代数是一种基础、典型的非线性代数,可以用来描述和处理各种非线性科学问题.多项式代数的经典内容在于建立存在性理论和方法,而非对具体代数与几何对象进行构造性研究.因为后者需要涉及大量复杂的多项式运算,常常会超出传统的纸上推演的可行范围.多项式代数的研究向构造性和算法化转变始于上个世纪60年代,从那时起,符号与代数计算的方法和软件快速发展,在计算机上进行大规模多项式运算变得现实可行.虽然用符号方法处理代数问题可以得到精确的完备解,但往往计算量大、表达式庞杂,导致存储空间增加,计算速度降低,因而远远达不到实际应用的需求.提出更高效的多项式代数算法,并用以有效解决各种理论和实际问题成了近年来多项式代数研究领域的主攻方向.稀疏插值是一种降低代数算法时间复杂度的有效方法,在结式计算、信号处理、压缩感知、不确定性量化等领域都有广泛应用.本文基于稀疏插值技术,研究了两个典型的多项式代数问题:结式消元和最大公因式(GCD)计算,提出了基于隐函数插值的结式消元法和基于稀疏多元多项式插值的最大公因式计算方法,并将基于隐函数插值的结式消元法应用于一类复杂的组合几何优化问题的求解.本文的主要研究内容如下:●研究了隐函数插值问题,设计并实现了隐函数插值算法.给出了隐函数插值的定义和描述,将隐函数插值问题转化为若干个多元有理函数插值问题,结合单变元有理函数插值和稀疏多元多项式插值恢复多元有理函数.针对单变元有理函数插值,采用了高概率算法结合提前终止技术的Cauchy插值法;针对稀疏多元多项式插值,采用了具有确定性多项式时间复杂度的Ben-Or/Tiwari算法.对于有理函数在零点无定义或退化情形,给出了有理函数分子或分母的常数项是否为零的一般性判别方法,并进行了相应的概率分析.●提出了基于隐函数插值的结式消元法,解决了纯符号或数值计算无法处理的一类复杂的非线性多元多项式方程组的求解问题.首先基于两个多元多项式的Sylvester结式,依次消去变元,并消去多余因子,通过给定某些变元的初始数值,结合消元过程构造单变元隐函数的黑盒,将结式消元问题转化为隐函数插值问题,使用隐函数插值算法恢复多项式系统的结式.●将基于隐函数插值的结式消元法应用于一类复杂的组合几何优化问题的求解.包括椭圆上三点构成的三角形的最大周长问题、Morley三等分定理、三角形三边上点构成的三角形最小周长问题.实验表明针对复杂的多项式系统求解问题,基于隐函数插值的结式消元法比纯符号消元更加有效.●研究了多元多项式最大公因式计算的稀疏插值算法.通过引入齐次变元,构造辅助多项式和转换辅助多项式,正规化目标GCD.首先利用关于齐次变元的单变元GCD计算获得目标GCD的稀疏结构,然后基于改进的Zippel算法或Ben-Or/Tiwari算法的稀疏多元多项式插值技术重建齐次变元的系数多项式,即月标GCD的各个齐次多项式.我们给出的插值算法不需要因式分解,对目标GCD的形式也不做任何限制.算法的复杂度与目标GCD的稀疏性及选择的稀疏多元多项式插值算法相关.●为进一步降低隐函数插值法、基于隐函数插值的结式消元法及多元多项式最大公因式计算的稀疏插值算法的时间复杂度,应用了概率和随机技术、模算术和有理向量恢复算法等.
其他文献
在实际应用中,响应变量为0-1离散变量的模型已成为一个日益重要的主题,在生活的方方面面都有诸多应用。本论文介绍了模型E(Y|X)=g(X)在参数模型、半参数模型及非参数模型下的不同情况,其中Y为0-1响应变量,X为p×1维自变量,9为某一函数。在参数模型及半参数模型下,我们考虑了g为自变量X的线性组合的函数的情形,分别对应了特殊形式下的广义线性模型及单指标模型。我们认为通过极小化一个凸性损失函数,
学术研究和工业应用领域存在许多具有大规模、非线性、超多目标等特征的优化问题。由于传统优化方法不能较好的解决这类复杂优化问题,因此启发式优化方法受到了研究者们的广泛关注,演化算法是这类方法中优化效果最好的方法之一。演化算法主要由解表示、种群初始化、停机条件、后代产生、选择等五个部分组成,并具有基于种群的搜索策略、随机搜索策略和目标函数驱动等三个特点。演化算法已成功应用于解决多种复杂优化问题,然而算法
因特网本身的体系结构已经和网络技术的发展与创新形成了不可调和的矛盾。为了从根本上解决上述问题,各种新型网络被先后提出,其中软件定义网络凭借其控制平面与数据平面解耦、使用开放的可编程接口和逻辑集中的控制等特性脱颖而出,被视为一种颇具前景的网络体系结构,受到了学术界和工业界的广泛关注。无论是对于因特网还是软件定义网络,故障都是一块巨大的绊脚石。虽然故障发生的频率一般不高,但一旦发生就可能对网络性能造成
本文主要研究了Cartan型李代数的Weyl群和半单轨道,以及Jacobson-Witt代数的几何.研究成果主要有:第四章得到了W,S,H型限制单李代数的Weyl群与半单轨道.第五章得到了Jacobson-Witt代数的完全Borel子代数的共轭类.第六章、第七章和第八章首先刻画了Jacobson-Witt代数的齐次旗簇、旗簇和Springer簇,然后初步研究了它们的性质.第九章研究了Witt代数
在过去的二十年里,人们为了提高非线性转换,把研究目光转移到与光场发生相互作用的原子介质上,通过光与原子协同作用来制备原子系统的量子相干实现增强非线性效应。光与原子协同作用的方式有很多,比如通过电磁感应透明过程制备的原子相干实现了效率较高的频率转换。同样,通过拉曼过程制备原子自旋波也实现了原子的量子相干,原子自旋波因为其在量子信息过程中应用的潜力吸引了很多的研究目光。近来采用原子自旋波作为“种子波”
本文基于符号计算软件Maple,利用对称性理论、相容Riccati方程展开法(CRE方法)、优化系统直接构造方法以及高阶对称延拓理论,研究了数学物理方程中若干非线性模型的相关问题,主要包含以下三方面的内容:若干非线性偏微分方程非局域对称及精确解的构造;优化系统的分类;暗方程的分类及递推算子的构造.具体章节安排如下:第一章绪论部分,介绍了本文研究内容的理论背景和发展现状,包括对称理论、优化系统、暗方
在本文中,我们研究了q-微分算子,q-分数阶微积分(q-分数阶莱布尼茨公式,q-分数阶积分,q-分数阶导数)以及一些q-多项式.同时我们也指出q-算子在基本超几何级数的应用中起着重要的作用.按照论文的顺序,主要结果如下:首先,我们引入本文中所涉及的关于基本超几何级数的一些定义,基本恒等式.详细介绍了q-导数,q-积分,q-莱布尼茨定理,q-求和公式以及最重要的q-二项式定理,它在许多恒等式的证明中
文章介绍肛周脓肿的术式改良选择及相应术后处理方法的临床应用情况。包括“单纯切开引流术、一次性根治术、切开挂线术、三间隙引流术、置管引流术、隧道式拖线术”在肛周脓肿的术式选择指征、操作要点及术后处理的注意事项。提示肛周脓肿因不同时机及脓肿范围深浅,选择不同手术方式及术后对应处理方法,在提高疗效的同时,注重肛门功能的保护,最终给患者提供个体化综合解决方案。
本论文由两章构成.在第一章我们研究正特征代数闭域上正交与辛型幂零轨道闭包的正规性.我们证明不包含d与e型不可约极小退化的幂零轨道闭包是正规的.相反包含e型极小不可约退化的幂零轨道闭包不正规.这里,极小不可约退化是Hesselink在[Hes]中给出的,一共有8种参见表1.1.我们的结果是复数域上的结果[KP2,定理16.2(ii)]在正特征域上较弱一点的版本.我们采用的证明方法是[KP2]中的Kr
纵向数据是一类重要的数据类型,它在社会学、经济学、生物医学、传染病学以及其它的自然科学领域有着广泛的应用。回归模型常用来研究协变量与响应变量间的相关关系。特别是,近年来非参和半参回归模型由于其灵活多变的特点以及能够挖掘实际问题中响应变量和相关协变量间潜在关系的能力而受到广泛的关注和研究。基于此,本文对纵向数据下非参半参回归模型的局部估计问题展开了若干研究,主要工作如下:(1)针对灵活多变且在纵向数