期刊文献+
共找到4篇文章
< 1 >
每页显示 20 50 100
基于模算术系数解析的稀疏插值算法
1
作者 唐敏 戚妞妞 邓国强 《计算机工程与科学》 CSCD 北大核心 2023年第4期599-606,共8页
稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略,被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法,其复杂度与多项式项数和次数相关,遇到大规模问题时由于执行多个高阶代数... 稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略,被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法,其复杂度与多项式项数和次数相关,遇到大规模问题时由于执行多个高阶代数运算而效率较低。提出一种新的求解稀疏多元多项式插值问题的算法,核心操作是利用模算术解析单变元多项式的系数,避免了传统方法必需的高阶方程组求解、高次方程求根等。该算法设定一变元为主元,将黑盒多元多项式视为该主元的单变元多项式,通过解析主元的系数多项式在不同插值点处的函数值,进而重构这些系数多项式以恢复整个多元多项式。理论分析和数值实验表明了算法的有效性和可行性。 展开更多
关键词 稀疏多元多项式插值 系数解析 ben-or/tiwari算法 模算术
下载PDF
确定性稀疏多元多项式插值算法的分析与实现
2
作者 张永燊 韦鹏 +1 位作者 吕少梅 王筱婷 《现代信息科技》 2020年第17期96-98,共3页
文章介绍了经典多元多项式插值算法及Ben-Or/Tiwari算法,在Matlab及Maple环境下实现了相应算法,给出了测试用例,对两种算法的CPU运行时间进行了比较,并将Ben-Or/Tiwari算法在有限域和非有限域下进行了实现。通过实验充分证明Ben-Or/Tiw... 文章介绍了经典多元多项式插值算法及Ben-Or/Tiwari算法,在Matlab及Maple环境下实现了相应算法,给出了测试用例,对两种算法的CPU运行时间进行了比较,并将Ben-Or/Tiwari算法在有限域和非有限域下进行了实现。通过实验充分证明Ben-Or/Tiwari算法可以解决较大规模的多项式插值问题,而且在有限域下该算法更为有效。 展开更多
关键词 稀疏多元多项式 多元多项式插值 ben-or/tiwari算法 有限域 非有限域
下载PDF
Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation
3
作者 TANG Min LI Bingyu ZENG Zhenbing 《Journal of Systems Science & Complexity》 SCIE EI CSCD 2018年第2期552-568,共17页
The problem of computing the greatest common divisor(GCD) of multivariate polynomials, as one of the most important tasks of computer algebra and symbolic computation in more general scope, has been studied extensiv... The problem of computing the greatest common divisor(GCD) of multivariate polynomials, as one of the most important tasks of computer algebra and symbolic computation in more general scope, has been studied extensively since the beginning of the interdisciplinary of mathematics with computer science. For many real applications such as digital image restoration and enhancement,robust control theory of nonlinear systems, L1-norm convex optimization in compressed sensing techniques, as well as algebraic decoding of Reed-Solomon and BCH codes, the concept of sparse GCD plays a core role where only the greatest common divisors with much fewer terms than the original polynomials are of interest due to the nature of problems or data structures. This paper presents two methods via multivariate polynomial interpolation which are based on the variation of Zippel's method and Ben-Or/Tiwari algorithm, respectively. To reduce computational complexity, probabilistic techniques and randomization are employed to deal with univariate GCD computation and univariate polynomial interpolation. The authors demonstrate the practical performance of our algorithms on a significant body of examples. The implemented experiment illustrates that our algorithms are efficient for a quite wide range of input. 展开更多
关键词 ben-or/tiwari algorithm multivariate polynomial interpolation sparse GCD Zippel's algorithm.
原文传递
An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials 被引量:4
4
作者 HUANG Qiaolong 《Journal of Systems Science & Complexity》 SCIE EI CSCD 2018年第2期539-551,共13页
This paper presents an improved early termination algorithm for sparse black box multivariate polynomials, which reduces the interpolation problem into several sub-interpolation problems with less variables and fewer ... This paper presents an improved early termination algorithm for sparse black box multivariate polynomials, which reduces the interpolation problem into several sub-interpolation problems with less variables and fewer terms. Actually, all interpolations are eventually reduced to the interpolation of a list of polynomials with less terms than that of the original polynomial. Extensive experiments show that the new algorithm is much faster than the original algorithm. 展开更多
关键词 ben-or and tiwari's algorithm early termination algorithm recursive sparse interpolation
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部