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

摘要：

稀疏多元多项式插值被广泛应用在科学和工程领域,目标是利用多项式的稀疏结构及其给定的离散信息恢复目标多项式.目前的主流方法在目标多项式规模较大时均表现出较高的时间复杂度,因其所需的代数操作的规模及个数与多项式的项数和次数相关.鉴于此,提出了一种求解稀疏多元多项式插值问题的有限域上的分治算法,其基本策略是视多项式中的一个变元为主元,其系数为关于其他变元的多元多项式,从而将原问题分解为一系列单变元多项式插值及规模远小于原问题的一系列子多元多项式插值问题,合并这些子多元多项式即得到原问题的解.为实现稀疏多元多项式插值分治算法,设计了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