张永燊 韦鹏 吕少梅 王筱婷
摘 要:文章介绍了经典多元多项式插值算法及Ben-Or/Tiwari算法,在Matlab及Maple环境下实现了相应算法,给出了测试用例,对两种算法的CPU运行时间进行了比较,并将Ben-Or/Tiwari算法在有限域和非有限域下进行了实现。通过实验充分证明Ben-Or/Tiwari算法可以解决较大规模的多项式插值问题,而且在有限域下该算法更为有效。
关键词:稀疏多元多项式;多元多项式插值;Ben-Or/Tiwari算法;有限域;非有限域
中图分类号:TP301.6,O241.3 文献标识码:A 文章编号:2096-4706(2020)17-0096-03
Abstract:This paper introduces the classic multivariate polynomial interpolation algorithm and the Ben-Or/Tiwari algorithm. The corresponding algorithm is implemented in the Matlab and Maple environment,and test cases are given. The CPU running time of the two algorithms is compared,and the Ben-Or/Tiwari algorithm is implemented in finite and non-finite fields. The experiment fully proves that the Ben-Or/Tiwari algorithm can solve large-scale polynomial interpolation. Problem,and the algorithm is more effective in a finite field.
Keywords:sparse multivariate polynomial;multivariate polynomial interpolation;Ben-Or/Tiwari algorithm;finite field;non-finite field
0 引 言
科学研究和实际应用领域中有许多来源于复杂系统的输入输出或算法构造的函数,它们往往容易求值却不易获得精确的数学表达式。这种数学表达式一般可以表达为这样的形式:令p是一个素数,f∈Zp(x1,x2,…,xn)是一个包含t(t>0)个非零项,用黑盒B:→?p表示的多元多项式。稀疏插值是重建此类黑盒函数的有效策略,特别是在计算机代数中,存在基于稀疏多元多项式插值的众多有效算法。
稀疏插值被广泛应用在数学和数值领域[1,2]及科学和工程领域[3],如指数分析、广义特征值问题、符号计算、信号处理等。将多元多项式表示为t个互不相同的单项式求和的形式,该多元多项式称为t稀疏多元多项式。稀疏插值的目标是通过较少的赋值次数(黑盒插值点),采用较低的时间复杂度,恢复多元多项式。
衡量插值算法的实用性,往往关注于算法的时间效率与空间效率,即:是否可通过较短的CPU运行时间对黑盒多项式进行恢复;算法是否对所需插值点要求严格以及所需插值点数量是否较少;在有限域及非有限域上,算法是否具有局限性等。与传统稠密多元多项式插值算法(如牛顿插值法)不同,针对多元多项式稀疏性的特点,稀疏多元多项式插值算法在解决此类问题时,往往更为实用。
1979年Zippel[4,5]提出了第一个用于求解GCD问题的概率性稀疏多元多项式插值算法,它是第一个具有多项式时间复杂度的算法。Zippel算法是许多主流的计算机代数系统中计算整系数多元多项式GCD的主要方法。1988年,Ben-Or和Tiwari提出了一个确定性稀疏插值算法[6],多项式系数可为整数,有理数,实数或是复数。
本文为国家级大学生创新训练计划项目相关课题,作者旨在研究Ben-Or/Tiwari算法与经典多项式插值算法的区别,主要读者对象为对插值问题有一定学习和了解的读者。本文在第1节和第2节中对经典的多元多项式插值算法(直接法)和Ben-Or/Tiwari算法进行了介绍,第3节给出了直接法和Ben-Or/Tiwari算法的算法运行时间进行了对比,并且设计相应数值实验,分别在有限域和非有限域下对确定性稀疏多元多项式插值算法——Ben-Or/Tiwari算法进行了实现,进行了相应的对比分析。
1 稠密多元多项式插值算法
2.1 非有限域下Ben-Or/Tiwari算法
结合上述Ben-Or/Tiwari算法的详细过程,可将非有限域下Ben-Or/Tiwari算法细致分为八个步骤:
2.2 有限域下Ben-Or/Tiwari算法
在2.1算法的基础上,对函数求值、求λ、构造函数求根和对根进行范德蒙行列式排列的时候,进行取模运算,降低矩阵元素的数值大小。
3 数值实验
对直接法和Ben-Or/Tiwari算法及其拓展与优化进行两两性能比较。直接法的编程环境为Matlab 2015,Ben-Or/Tiwari算法的编程环境为Maple 2018。注意两个程序都是顺序执行,在确定变元X1,X2,…,Xn的次数时未并行化。本章给出了3组测试集的性能比较结果,使用的多项式都是随机生成的,比较的对象为CPU运行时间。黑盒中的多元多项式系数取自?p,其中p=100。
3.1 测试集#1
本组测试集为2个变元3次多元多项式,项数t=3,次数从3变化到4。将直接法与有限域上的Ben-Or/Tiwari算法性能与时间做比较。
本组问题集包含2个变元的3次多元多项式,多项式的通项为幂级数排列,其中最多项数为dn=16。取项数t=4,所以令多元多项式P=x13-3x12x2+3x1x22-x23。通过Matlab求解可得到表1系数对应表,原多元多项式的系数矩阵刚好匹配。其中ai,i=0,1,2,…,15为各待求多项式的系数,共有dn=16项。
记录每个多项式在两种算法下的运行时间(s),如表2所示。表头第1列d表示最高项的次数;第2列t表示项数。
从表2可以看出,Ben-Or/Tiwari算法比直接法耗时更短,且随着次数的增加,两种算法的执行时间也随之增加,但Ben-Or/Tiwari算法对次数变化不敏感。
3.2 测试集#2
本组测试集通过物理学上的控制单一变量法,分别固定了多元多项式的次数、变元、项数,然后对其他的变量进行有规律的穷举,得到不同域上的算法时间复杂度。
通过表3可以看出,在固定次数的基础上改变它的变元个数及项数,两种数域下的时间复杂度都会提升,而有限域比非有限域的提升速度较慢,所以有限域在一定程度上较非有限域受到的影响更小。
通过表4可以看出,在固定变元的基础上改变多元多项式的另外两个变量时,仍是有限域与非有限域的时间复杂度均有提升,但有限域对变量的改变更不敏感。
通过表5可以看出,在固定项数的基础上改变多元多项式的另外两个变量时,与表3和表4的有限域与非有限域的时间复杂度均有提升有差别,此时有限域的时间复杂度保持不变,而非有限域的时间复杂度先上升后下降最后保持不变,造成这样结果的原因是:在有限域的算法上对矩阵上的元素都进行了取模运算,保证了取模后的元素都在一定范围内,而非有限域上的元素是没有限制的,因此在求解矩阵的运算时,耗费的时间大。所以当变元的次数、变元的个数已以递增的形式变化时,非有限域上的算法运算度以指数级增大。
4 结 论
本文介绍了经典的多元多项式插值算法(直接法),并给出了有限域上、非有限域上求解稀疏多元多项式插值算法。其中直接法可以解决小变元、小次数的多元多项式的插值,但是当其变元次数、个数增加时,时间效率低,速度慢。非有限域、有限域上的稀疏多元多项式插值算法Ben-Or/Tiwari算法,根据黑盒赋值恢复目标多项式,实现对多变元多项式的插值。在有限域上可以进行各种代数运算,有助于提高运算速度。最后使用有理数恢复算法即可复原目标多项式,在非有限域上可以把使用范围扩大,但是相对于有限域上的Ben-Or/Tiwari算法,其运算速度次之,相对于直接法,其运算速度比较快。数值实验中,通过变元次数、项数和个数的变化来测试本文算法的时间性能。结果表明,在一定条件有限域和非有限域下的Ben-Or/Tiwari算法都能在较短时间内求解较小规模的黑盒多元多项式插值问题,并具有内在的可并行性。相比于直接法而言,Ben-Or/Tiwari算法具有较低的时间复杂度和空间复杂度,且实验证明了有限域下,Ben-Or/Tiwari算法更为有效。
参考文献:
[1] PLONKA G,WANNENWETSCH K,CUYT A,et al. Deterministic Sparse FFT for M-Sparse Vectors [J].Numerical Algorithms,2018,78(1):133-159.
[2] 唐敏,邓国强.有限域上稀疏多元多项式插值算法 [J].计算机科学与探索,2019,13(2):350-360.
[3] ISTRATOV A A,VYVENKO O F. Exponential Analysis in Physical Phenomena [J].Review of Scientific Instruments,1999,70(2):1233-1257.
[4] ZIPPEL R. Interpolating Polynomials From Their Values [J].Journal of Symbolic Computation,1990,9(3):375-403.
[5] ZIPPEL R. Probabilistic Algorithms for Sparse Polynomials [C]// Eurosam79,An International Symposium on Symbolic and Algebraic Manipulation.Heidelberg:Springer,1979:216-226.
[6] BEN-OR M,TIWARI P. A deterministic algorithm for sparse multivariate polynomial interpolation [C]//STOC88:Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.New York:Association for Computing Machinery,1988:301-309.
作者简介:张永燊(1996—),男,汉族,河北成安人,硕士研究生,研究方向:稀疏插值。