-
题名求解稀疏多元多项式插值问题的分治算法
被引量:3
- 1
-
-
作者
邓国强
唐敏
梁状昌
-
机构
桂林电子科技大学广西密码学与信息安全重点实验室
-
出处
《计算机科学》
CSCD
北大核心
2019年第5期298-303,共6页
-
基金
广西科技基地和人才专项(桂科AD18281024)
广西高校中青年教师基础能力提升项目(2019KY0210
+1 种基金
2018KY0210)
国家级大学生创新训练计划项目(201810595024)资助
-
文摘
稀疏多元多项式插值被广泛应用在科学和工程领域,目标是利用多项式的稀疏结构及其给定的离散信息恢复目标多项式。目前的主流方法在目标多项式规模较大时均表现出较高的时间复杂度,因其所需的代数操作的规模及个数与多项式的项数和次数相关。鉴于此,提出了一种求解稀疏多元多项式插值问题的有限域上的分治算法,其基本策略是视多项式中的一个变元为主元,其系数为关于其他变元的多元多项式,从而将原问题分解为一系列单变元多项式插值及规模远小于原问题的一系列子多元多项式插值问题,合并这些子多元多项式即得到原问题的解。为实现稀疏多元多项式插值分治算法,设计了4个子算法:基于提前终止策略的单变元多项式插值算法、已知次数的单变元多项式插值算法、多项式项数判定的Hankle矩阵行列式检测法、已知项数的Ben-Or/Tiwari算法。对新算法与Zippel算法、Ben-Or/Tiwari算法、 Javadi/Monagan算法进行了数值实验比较,结果表明所提算法在运行时间上有较大的改进。实验数据充分说明:提前终止策略的运用,消除了必须给定目标多项式的项数界和次数界的限制;分治策略的运用,将大量高阶的代数运算分解为低阶问题,从而有效地解决了大规模多元多项式插值问题的时间性能瓶颈。
-
关键词
稀疏多元多项式插值
分治算法
提前终止策略
HANKEL矩阵
-
Keywords
Sparse multivariate polynomial interpolation
Divide-and-conquer algorithm
Early termination strategy
Hankel matrix
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
O241.3
[理学—计算数学]
-
-
题名一种基于竞争策略的稀疏多元多项式插值算法
被引量:1
- 2
-
-
作者
邓国强
唐敏
张永燊
-
机构
桂林电子科技大学广西密码学与信息安全重点实验室
-
出处
《系统科学与数学》
CSCD
北大核心
2018年第12期1436-1448,共13页
-
基金
国家自然科学基金(11561015)
广西科技基地和人才专项(2018AD19050)
+2 种基金
广西高校中青年教师基础能力提升项目(2018KY0210)
广西密码学与信息安全重点实验室研究课题(GCIS201615)
国家级大学生创新训练计划项目(201810595024)资助课题
-
文摘
提出了一个有限域上的基于竞争策略的稀疏多元多项式插值算法,改进了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运行时间进行了比较.
-
关键词
稀疏多元多项式插值
竞争策略
Javadi/Monagan算法
Zippel算法
-
Keywords
Sparse multivariate polynomial interpolation
Racing strategy
Javadi/ Monagan algorithm
Zippel's algorithm
-
分类号
O241.3
[理学—计算数学]
-
-
题名基于模算术系数解析的稀疏插值算法
- 3
-
-
作者
唐敏
戚妞妞
邓国强
-
机构
桂林电子科技大学数学与计算科学学院广西高校数据分析与计算重点实验室
-
出处
《计算机工程与科学》
CSCD
北大核心
2023年第4期599-606,共8页
-
基金
国家自然科学基金(11761024)
广西科技基地和人才专项(AD18281024)
桂林电子科技大学研究生优秀学位论文培养项目(2020YJSPYB02)。
-
文摘
稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略,被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法,其复杂度与多项式项数和次数相关,遇到大规模问题时由于执行多个高阶代数运算而效率较低。提出一种新的求解稀疏多元多项式插值问题的算法,核心操作是利用模算术解析单变元多项式的系数,避免了传统方法必需的高阶方程组求解、高次方程求根等。该算法设定一变元为主元,将黑盒多元多项式视为该主元的单变元多项式,通过解析主元的系数多项式在不同插值点处的函数值,进而重构这些系数多项式以恢复整个多元多项式。理论分析和数值实验表明了算法的有效性和可行性。
-
关键词
稀疏多元多项式插值
系数解析
Ben-Or/Tiwari算法
模算术
-
Keywords
sparse multivariate polynomial interpolation
coefficient parsing
Ben-Or/Tiwari algorithm
modular arithmetic
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名一种基于多样化多项式的高概率稀疏插值算法
被引量:1
- 4
-
-
作者
戚妞妞
唐敏
邓国强
-
机构
桂林电子科技大学数学与计算科学学院广西密码学与信息安全重点实验室
-
出处
《系统科学与数学》
CSCD
北大核心
2021年第12期3324-3341,共18页
-
基金
广西科技基地和人才专项(AD18281024)
广西密码学与信息安全重点实验室研究课题(GCIS201821)
桂林电子科技大学研究生优秀学位论文培养项目(2020YJSPYB02)资助课题。
-
文摘
稀疏多元多项式插值用于构造黑盒函数,是求解多项式代数问题的一种有效策略,具有多项式时间复杂度的多元稀疏插值算法已得到广泛研究和使用.近期Huang(2021)提出了一个基于多样化多项式的稀疏插值算法,计算复杂度为O(nTlog^(2)q+nT√Dlogq),是有限域上首个关于变元个数n和项数界T的线性函数,关于次数界D的分数次幂的高效算法.由于Huang算法准确恢复黑盒多项式的成功率为3/4,为提高插值成功率,文章分析了Huang算法不能准确恢复黑盒多项式的三种情形,并给出相应的解决方案,基于此设计了一种基于多样化多项式的高概率稀疏插值算法,理论分析和数值实验证实了算法的可行性和有效性.
-
关键词
稀疏多元多项式插值
多样化多项式
原根
离散对数
-
Keywords
Sparse multivariate polynomial interpolation
diversification polynomial
primitive root
discrete logarithm
-
分类号
O174.14
[理学—基础数学]
-