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

摘要：

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

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

所属期刊栏目：13

分类号：TP301(计算技术、计算机技术)

在线出版日期：2019-04-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：350-360