期刊专题

10.11896/j.issn.1002-137X.2019.05.046

求解稀疏多元多项式插值问题的分治算法

引用
稀疏多元多项式插值被广泛应用在科学和工程领域,目标是利用多项式的稀疏结构及其给定的离散信息恢复目标多项式.目前的主流方法在目标多项式规模较大时均表现出较高的时间复杂度,因其所需的代数操作的规模及个数与多项式的项数和次数相关.鉴于此,提出了一种求解稀疏多元多项式插值问题的有限域上的分治算法,其基本策略是视多项式中的一个变元为主元,其系数为关于其他变元的多元多项式,从而将原问题分解为一系列单变元多项式插值及规模远小于原问题的一系列子多元多项式插值问题,合并这些子多元多项式即得到原问题的解.为实现稀疏多元多项式插值分治算法,设计了4个子算法:基于提前终止策略的单变元多项式插值算法、已知次数的单变元多项式插值算法、多项式项数判定的Hankle矩阵行列式检测法、已知项数的Ben-Or/Tiwari算法.对新算法与Zip-pel算法、Ben-Or/Tiwari算法、Javadi/Monagan算法进行了数值实验比较,结果表明所提算法在运行时间上有较大的改进.实验数据充分说明:提前终止策略的运用,消除了必须给定目标多项式的项数界和次数界的限制;分治策略的运用,将大量高阶的代数运算分解为低阶问题,从而有效地解决了大规模多元多项式插值问题的时间性能瓶颈.

稀疏多元多项式插值、分治算法、提前终止策略、Hankel矩阵

46

TP301.6;O241.3(计算技术、计算机技术)

广西科技基地和人才专项桂科AD18281024;广西高校中青年教师基础能力提升项目2019KY0210,2018KY0210;国家级大学生创新训练计划项目201810595024

2019-06-05(万方平台首次上网日期,不代表论文的发表时间)

共6页

298-303

暂无封面信息
查看本期封面目录

计算机科学

1002-137X

50-1075/TP

46

2019,46(5)

专业内容知识聚合服务平台

国家重点研发计划“现代服务业共性关键技术研发及应用示范”重点专项“4.8专业内容知识聚合服务技术研发与创新服务示范”

国家重点研发计划资助 课题编号:2019YFB1406304
National Key R&D Program of China Grant No. 2019YFB1406304

©天津万方数据有限公司 津ICP备20003920号-1

信息网络传播视听节目许可证 许可证号:0108284

网络出版服务许可证:(总)网出证(京)字096号

违法和不良信息举报电话:4000115888    举报邮箱:problem@wanfangdata.com.cn

举报专区:https://www.12377.cn/

客服邮箱:op@wanfangdata.com.cn