求解稀疏多元多项式插值问题的分治算法

摘要/Abstract

摘要： 稀疏多元多项式插值被广泛应用在科学和工程领域,目标是利用多项式的稀疏结构及其给定的离散信息恢复目标多项式。目前的主流方法在目标多项式规模较大时均表现出较高的时间复杂度,因其所需的代数操作的规模及个数与多项式的项数和次数相关。鉴于此,提出了一种求解稀疏多元多项式插值问题的有限域上的分治算法,其基本策略是视多项式中的一个变元为主元,其系数为关于其他变元的多元多项式,从而将原问题分解为一系列单变元多项式插值及规模远小于原问题的一系列子多元多项式插值问题,合并这些子多元多项式即得到原问题的解。为实现稀疏多元多项式插值分治算法,设计了4个子算法:基于提前终止策略的单变元多项式插值算法、已知次数的单变元多项式插值算法、多项式项数判定的Hankle矩阵行列式检测法、已知项数的Ben-Or/Tiwari算法。对新算法与Zippel算法、Ben-Or/Tiwari算法、 Javadi/Monagan算法进行了数值实验比较,结果表明所提算法在运行时间上有较大的改进。实验数据充分说明:提前终止策略的运用,消除了必须给定目标多项式的项数界和次数界的限制;分治策略的运用,将大量高阶的代数运算分解为低阶问题,从而有效地解决了大规模多元多项式插值问题的时间性能瓶颈。

关键词: Hankel矩阵, 分治算法, 提前终止策略, 稀疏多元多项式插值

Abstract: Sparse interpolation is widely used in quite different applications and areas of science and engineering.Its goal is to recover the goal polynomial by taking advantage of the sparse structure of the polynomial and given discrete va-lues.For polynomials with the large size,the current methods show high time complexity,because the size and the number of algebra operations are related to the number of terms and the total degree of the goal polynomials.For this reason,this paper presented a divide-and-conquer algorithm for sparse polynomial interpolation over finite fields.The basic strategy is to choose one of variables as the main variable and the coefficients are multivariate polynomials in other variables.In this way,the original polynomial interpolation is divided into a list of univariate polynomial interpolations and a list of sub-polynomials with smaller size.The solution of the original problem is to merge these sub-polynomials.To implement the divide-and-conquer strategy for the sparse polynomial interpolation,this paper designed four sub-algorithms:univariate polynomial interpolation based on early termination strategy,univariate polynomial interpolation with a prior knowledge of the total degrees of the polynomial,the determination of the number of terms of the polynomial via Hankle matrix determinant,and Ben-Or/Tiwari’s algorithm with an upper bound of the number of terms.In numerical experiments,the performance of the new algorithm is compared with that of Zippel’s algorithm,Ben-Or/Tiwari’s algorithm and Javadi/Monagan’s algorithm.Extensive experiments show that the new algorithm is much faster than other three algorithms.The experimental data demonstrate that the use of divide-and-conquer and early termination strategy not only eliminates some priori knowledge of the total degree and the number of terms of the goal polynomials,but also decomposes a large number of higher order algebra operations into smaller ones.Therefore,the bottleneck of the large-scale multivariate polynomial interpolation problems is effectively solved.

Key words: Divide-and-conquer algorithm, Early termination strategy, Hankel matrix, Sparse multivariate polynomial interpolation

中图分类号:

TP301.6

邓国强, 唐敏, 梁状昌. 求解稀疏多元多项式插值问题的分治算法[J]. 计算机科学, 2019, 46(5): 298-303. https://doi.org/10.11896/j.issn.1002-137X.2019.05.046

DENG Guo-qiang, TANG Min, LIANG Zhuang-chang. Divide-and-Conquer Algorithm for Sparse Polynomial Interpolation[J]. Computer Science, 2019, 46(5): 298-303. https://doi.org/10.11896/j.issn.1002-137X.2019.05.046

参考文献

[1]CUYT A,LEE W.Sparse interpolation and rational approximation[M]∥Modern Trends in Constructive Function Theory.2016:229-242.
[2]CUYT A,LEE W,WANG X.On tensor decomposition,sparse interpolation and Padé approximation[J].Jaen Journal on Approximation,2016,8(1):33-58.
[3]HU J,MONAGAN M.A fast parallel sparse polynomial GCD algorithm[J].Journal of the ACM,2017,1(1):1-41.
[4]MONAGAN M,TUNCER B.Using Sparse Interpolation inHensel Lifting[C]∥International Workshop on Computer Algebra in Scientific Computing.Bucharest:Springer,2016:381-400.
[5]BRIANI M,CUYT A,LEE W.Sparse Interpolation,the FFTAlgorithm and FIR Filters[C]∥International Workshop on Computer Algebra in Scientific Computing.Cham:Springer,2017:27-39.
[6]PLONKA G,WANNENWETSCH K,CUYT A,et al.Deter-ministic sparse FFT for M-sparse vectors[J].Numerical Algorithms,2018,78(1):133-159.
[7]ISTRATOV A,VYVENKO O.Exponential analysis in physical phenomena[J].Review of Scientific Instruments,1999,70(2):1233-1257.
[8]ZIPPEL R.Probabilistic algorithms for sparse polynomials.
Symbolic and Algebraic Computation[M]∥Symbolic and Algebraic Computation.Berlin:Springer,1979:216-226.
[9]BEN-OR M,TIWARI P.A deterministic algorithm for sparsemultivariate polynomial interpolation[C]∥Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.New York:ACM,1988:301-309.
[10]GRIGORIEV D,KARPINSKI M,SINGER M.Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields[J].SIAM Journal on Computing,1990,19(6):1059-1063.
[11]HUANG M,RAO A.Interpolation of sparse multivariate polynomials over large finite fields with applications[J].Journal of Algorithms,1999,33(2):204-228.
[12]RAYES M,WANG P,WEBER K.Parallelization of the sparse modular GCD algorithm for multivariate polynomials on shared memory multiprocessors[C]∥ Proceedings of the International Symposium on Symbolic and Algebraic Computation.New York,NY,USA:ACM,1994:66-73.
[13]KALTOFEN E,LEE W.Early termination in sparse interpolation algorithms[J].Journal of Symbolic Computation,2003,36(3-4):365-400.
[14]KALTOFEN E,LEE W,LOBO A.Early termination in Ben-or/Tiwari sparse interpolation and a hybrid of Zippel’s algorithm[C]∥Proceedings of the International Symposium on Symbolic and Algebraic Computation.New York,ACM:2000:192-201.
[15]JAVADI S,MONAGAN M.Parallel sparse polynomial interpolation over finite fields[C]∥Proceedings of the 4th International Workshop on Parallel and Symbolic Computation.New York,ACM:2010:160-168.
[16]ARNOLD A,GIESBRECHT M,ROCHE D.Faster sparse multi-variate polynomial interpolation of straight-line programs[J].Journal of Symbolic Computation,2016,75:4-24.
[17]ARNOLD A,GIESBRECHT M,ROCHE D.Sparse interpola-tion over finite fields via low-order roots of unity[C]∥ International Symposium on Symbolic and Algebraic Computation.ACM,2014:27-34.
[18]CUYT A,LEE W.Multivariate exponential analysis from the minimal number of samples[J].Advances in Computational Mathematics,2017(9):1-16.
[19]HAO Z,KALTOFEN E,ZHI L.Numerical Sparsity Determination and Early Termination[C]∥ACM on International Symposium on Symbolic and Algebraic Computation.ACM,2016:247-254.
[20]HUANG Q L.An improved early termination sparse interpolation algorithm for multivariate polynomials[J].Journal of Systems Science and Complexity,2018,31(2):1-13.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed