期刊文献+
共找到2篇文章
< 1 >
每页显示 20 50 100
基于模算术系数解析的稀疏插值算法
1
作者 唐敏 戚妞妞 邓国强 《计算机工程与科学》 CSCD 北大核心 2023年第4期599-606,共8页
稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略,被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法,其复杂度与多项式项数和次数相关,遇到大规模问题时由于执行多个高阶代数... 稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略,被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法,其复杂度与多项式项数和次数相关,遇到大规模问题时由于执行多个高阶代数运算而效率较低。提出一种新的求解稀疏多元多项式插值问题的算法,核心操作是利用模算术解析单变元多项式的系数,避免了传统方法必需的高阶方程组求解、高次方程求根等。该算法设定一变元为主元,将黑盒多元多项式视为该主元的单变元多项式,通过解析主元的系数多项式在不同插值点处的函数值,进而重构这些系数多项式以恢复整个多元多项式。理论分析和数值实验表明了算法的有效性和可行性。 展开更多
关键词 稀疏多元多项式插值 系数解析 Ben-Or/Tiwari算法 模算术
下载PDF
一种基于多样化多项式的高概率稀疏插值算法 被引量:1
2
作者 戚妞妞 唐敏 邓国强 《系统科学与数学》 CSCD 北大核心 2021年第12期3324-3341,共18页
稀疏多元多项式插值用于构造黑盒函数,是求解多项式代数问题的一种有效策略,具有多项式时间复杂度的多元稀疏插值算法已得到广泛研究和使用.近期Huang(2021)提出了一个基于多样化多项式的稀疏插值算法,计算复杂度为O(nTlog^(2)q+nT√Dlo... 稀疏多元多项式插值用于构造黑盒函数,是求解多项式代数问题的一种有效策略,具有多项式时间复杂度的多元稀疏插值算法已得到广泛研究和使用.近期Huang(2021)提出了一个基于多样化多项式的稀疏插值算法,计算复杂度为O(nTlog^(2)q+nT√Dlogq),是有限域上首个关于变元个数n和项数界T的线性函数,关于次数界D的分数次幂的高效算法.由于Huang算法准确恢复黑盒多项式的成功率为3/4,为提高插值成功率,文章分析了Huang算法不能准确恢复黑盒多项式的三种情形,并给出相应的解决方案,基于此设计了一种基于多样化多项式的高概率稀疏插值算法,理论分析和数值实验证实了算法的可行性和有效性. 展开更多
关键词 稀疏多元多项式插值 多样化多项式 原根 离散对数
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部