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

发布时间：2017-12-08 03:28

  本文关键词：基于稀疏插值的多项式代数算法及其应用

  更多相关文章： 隐函数插值 稀疏有理函数插值 稀疏多元多项式插值 结式消元 最大公因式 组合几何优化

【摘要】：多项式代数是一种基础、典型的非线性代数,可以用来描述和处理各种非线性科学问题.多项式代数的经典内容在于建立存在性理论和方法,而非对具体代数与几何对象进行构造性研究.因为后者需要涉及大量复杂的多项式运算,常常会超出传统的纸上推演的可行范围.多项式代数的研究向构造性和算法化转变始于上个世纪60年代,从那时起,符号与代数计算的方法和软件快速发展,在计算机上进行大规模多项式运算变得现实可行.虽然用符号方法处理代数问题可以得到精确的完备解,但往往计算量大、表达式庞杂,导致存储空间增加,计算速度降低,因而远远达不到实际应用的需求.提出更高效的多项式代数算法,并用以有效解决各种理论和实际问题成了近年来多项式代数研究领域的主攻方向.稀疏插值是一种降低代数算法时间复杂度的有效方法,在结式计算、信号处理、压缩感知、不确定性量化等领域都有广泛应用.本文基于稀疏插值技术,研究了两个典型的多项式代数问题:结式消元和最大公因式(GCD)计算,提出了基于隐函数插值的结式消元法和基于稀疏多元多项式插值的最大公因式计算方法,并将基于隐函数插值的结式消元法应用于一类复杂的组合几何优化问题的求解.本文的主要研究内容如下:●研究了隐函数插值问题,设计并实现了隐函数插值算法.给出了隐函数插值的定义和描述,将隐函数插值问题转化为若干个多元有理函数插值问题,结合单变元有理函数插值和稀疏多元多项式插值恢复多元有理函数.针对单变元有理函数插值,采用了高概率算法结合提前终止技术的Cauchy插值法;针对稀疏多元多项式插值,采用了具有确定性多项式时间复杂度的Ben-Or/Tiwari算法.对于有理函数在零点无定义或退化情形,给出了有理函数分子或分母的常数项是否为零的一般性判别方法,并进行了相应的概率分析.●提出了基于隐函数插值的结式消元法,解决了纯符号或数值计算无法处理的一类复杂的非线性多元多项式方程组的求解问题.首先基于两个多元多项式的Sylvester结式,依次消去变元,并消去多余因子,通过给定某些变元的初始数值,结合消元过程构造单变元隐函数的黑盒,将结式消元问题转化为隐函数插值问题,使用隐函数插值算法恢复多项式系统的结式.●将基于隐函数插值的结式消元法应用于一类复杂的组合几何优化问题的求解.包括椭圆上三点构成的三角形的最大周长问题、Morley三等分定理、三角形三边上点构成的三角形最小周长问题.实验表明针对复杂的多项式系统求解问题,基于隐函数插值的结式消元法比纯符号消元更加有效.●研究了多元多项式最大公因式计算的稀疏插值算法.通过引入齐次变元,构造辅助多项式和转换辅助多项式,正规化目标GCD.首先利用关于齐次变元的单变元GCD计算获得目标GCD的稀疏结构,然后基于改进的Zippel算法或Ben-Or/Tiwari算法的稀疏多元多项式插值技术重建齐次变元的系数多项式,即月标GCD的各个齐次多项式.我们给出的插值算法不需要因式分解,对目标GCD的形式也不做任何限制.算法的复杂度与目标GCD的稀疏性及选择的稀疏多元多项式插值算法相关.●为进一步降低隐函数插值法、基于隐函数插值的结式消元法及多元多项式最大公因式计算的稀疏插值算法的时间复杂度,应用了概率和随机技术、模算术和有理向量恢复算法等.
【学位授予单位】：华东师范大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O174.14

【相似文献】

中国期刊全文数据库 前10条

1 何月顺;在有序表中搜索插值点[J];华东地质学院学报;1999年04期

2 李宁;三点插值参数估计法及其在生产中的应用[J];物理;1986年01期

3 徐庆荣;;曲线插值中步长的确定[J];武汉测绘学院学报;1983年01期

4 王翔;关于四次缺插值样条函数[J];浙江大学学报;1985年02期

5 郭竹瑞,叶懋冬,黄达人;高次样条循环插值的收敛阶[J];数学年刊A辑(中文版);1985年02期

6 蔺青冲 ,袁志范 ,叶文洪;一类对称插值样条和严格凸插值样条[J];信阳师范学院学报(自然科学版);1991年04期

7 沈燮昌;复平面上Hermite插值多项式的同时逼近阶[J];河南大学学报(自然科学版);1991年02期

8 汪嘉业,张彩明;散乱空间数据点的插值[J];高校应用数学学报A辑(中文版);1987年04期

9 邱钧,孙洪泉,韩伟;二元正态分布函数(Coons曲面法)插值研究[J];工程图学学报;2002年03期

10 贾荣庆;Kergin插值算子的扩张[J];科学通报;1986年11期

中国重要会议论文全文数据库 前3条

1 韩靖;韩旭里;;曲线插值的一种具有还圆性的细分方法[A];第五届全国几何设计与计算学术会议论文集[C];2011年

2 邓四清;王平;谢进;;一类有理四次插值样条曲线的形状控制[A];第三届和谐人机环境联合学术会议（HHME2007）论文集[C];2007年

3 左小伟;王杰光;;改进Shepard插值无网格配点法[A];第17届全国结构工程学术会议论文集（第Ⅰ册）[C];2008年

中国博士学位论文全文数据库 前4条

1 汪成峰;基于自适应关节权重和插值小波的体感动作评价方法研究[D];中国农业大学;2016年

2 唐敏;基于稀疏插值的多项式代数算法及其应用[D];华东师范大学;2017年

3 CAMARA AMARA;曲线曲面插值模型的研究[D];中南大学;2007年

4 高文武;拟插值的若干理论及其应用[D];复旦大学;2012年

中国硕士学位论文全文数据库 前10条

1 赵菲;基于Peterson模型的京津冀地区AOD时空插值研究[D];河北师范大学;2016年

2 蒋磊;一类拟细分插值基函数的构造探究[D];浙江工商大学;2017年

3 钱昕f，

本文编号：1264881