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

• 作者: 唐敏 梁状昌 邓国强
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 稀疏多元多项式插值 分治算法 提前终止策略 Hankel矩阵
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 交叉与前沿
• 页码范围: 298-303
• 页数: 6页
• 分类号: TP301.6|O241.3
• 字数: 7324字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2019.05.046

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐敏	桂林电子科技大学广西密码学与信息安全重点实验室	16	48	3.0	6.0
2	邓国强	桂林电子科技大学广西密码学与信息安全重点实验室	14	43	3.0	6.0
3	梁状昌	桂林电子科技大学广西密码学与信息安全重点实验室	1	0	0.0	0.0