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

作者：邓国强; 唐敏^*; 张永燊

来源：系统科学与数学, 2018, 38(12): 1436-1448.

• 稀疏多元多项式插值
• 竞争策略
• Javadi/Monagan算法
• Zippel算法

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

• 单位
  桂林电子科技大学