有限域上稀疏多元多项式插值算法

• 作者: 唐敏 邓国强
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 稀疏插值 多元多项式 Javadi/Monagan算法 二部图 完美匹配
• 年，卷（期）: 2019,（2）
• 所属期刊栏目: 理论与算法
• 页码范围: 350-360
• 页数: 11页
• 分类号: TP301
• 字数: 9290字
• 语种: 中文

摘要

稀疏插值是一种降低计算机代数算法时间复杂度的有效方法,在信号处理、压缩感知、结式计算、图像处理等领域都有广泛应用.为了提高稀疏多元多项式插值算法的效率,对Javadi/Monagan稀疏插值算法进行了改进.首先,消除了必须预先给定项数界T的限制,通过计算特定的矩阵行列式,得到插值多项式 f 的准确项数.然后,消除了必须预先给定次数界D的限制,通过构造辅助函数,利用概率法结合提前终止技术的Cauchy插值法,得到插值多项式 f 的准确次数,解决了Javadi和Monagan论文中提出的次数界D过高而导致的高计算复杂度的问题.理论分析和实验结果表明了改进算法的优势,特别是在给定的次数界D过高的情况下,相较于Javadi/Monagan算法,改进算法的性能有较大提高.更进一步,由于改进算法无须给定项数界T和次数界D,对于实际问题在利用插值恢复或近似时更具实用性.

作者信息

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