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

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

一种基于竞争策略的稀疏多元多项式插值算法

提出了一个有限域上的基于竞争策略的稀疏多元多项式插值算法,改进了Javadi和Monagan在2010年提出的概率性插值算法.对n个变元,t个非零项的多元多项式f进行插值,Javadi/Monagan算法要求给定f的全次数上界d,为确定变元x_j在第i个单项式中的次数,需要从O到d做d+1次根测试,每个变元测试次数为O(td).改进算法设计了两个子算法并采用竞争策略用尽可能少的插值点准确计算变元x_j在多项式f中的次数集,使得测试次数降为O(td'),其中d'为变元x_j在f中出现的次数集的基数,因而减小了测试次数及根冲突的概率.在Maple环境下实现了改进算法,Zippel算法和Javadi/Monagan算法,给出了测试用例对3种算法的插值点个数及其CPU运行时间进行了比较.