Computer Science ›› 2019, Vol. 46 ›› Issue (5): 298-303.doi: 10.11896/j.issn.1002-137X.2019.05.046

Previous Articles     Next Articles

Divide-and-Conquer Algorithm for Sparse Polynomial Interpolation

DENG Guo-qiang, TANG Min, LIANG Zhuang-chang   

  1. (Guangxi Key Laboratory of Cryptography and Information Security,Guilin University of Electrical Technology,Guilin,Guangxi 541004,China)
  • Published:2019-05-15

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: Sparse multivariate polynomial interpolation, Divide-and-conquer algorithm, Early termination strategy, Hankel matrix

CLC Number: 

  • TP301.6
[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.
[1] ZHANG Meng HE Kai-cheng HAN Wen-bao ZENG Guang (Department of Information Research, Information Engineering University, Zhengzhou 450002, China). [J]. Computer Science, 2008, 35(12): 119-121.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .