计算机科学与探索

作者：唐敏，邓国强

单位：桂林电子科技大学 数学与计算科学学院 广西密码学与信息安全重点实验室，广西 桂林 541004

关键词：稀疏插值,多元多项式,Javadi/Monagan算法,二部图,完美匹配

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

来源：2019年第2期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2019年第2期