Sparse Polynomial Interpolation Based on Diversification with High Probability

QI Niuniu, TANG Min, DENG Guoqiang

Journal of Systems Science and Mathematical Sciences ›› 2021, Vol. 41 ›› Issue (12) : 3324-3341.

PDF(668 KB)
中国科学院数学与系统科学研究院期刊网
PDF(668 KB)
Journal of Systems Science and Mathematical Sciences ›› 2021, Vol. 41 ›› Issue (12) : 3324-3341. DOI: 10.12341/jssms21400

Sparse Polynomial Interpolation Based on Diversification with High Probability

  • QI Niuniu, TANG Min, DENG Guoqiang
Author information +
History +

Abstract

Interpolation strategies have shown to be very effective in the reconstruction black-box functions, in particular in polynomial algebra, for sparse multivariate polynomials. In addition, sparse multivariate interpolation algorithms with polynomial time complexity have been widely studied and applied. Recently, Huang(2021) presented a sparse polynomial interpolation algorithm based on diversification. The algorithm costs O(nTlog2⁡q+nTDlog⁡q) bit operations and it is the first one to achieve the complexity of fractional power about D, while keeping linear in n, T over finite fields Fq. Since Huang's algorithm is probabilistic with correct interpolates f with probability at lest 34, in order to improve the success probabilistic of interpolation, three failure cases of Huang's algorithm are analyzed, and the corresponding modification schemes are given. Based on revised strategies, a high probability sparse interpolation algorithm based on diversified polynomial is designed. Extensive numerical experiments show the effectiveness of the algorithm.

Key words

Sparse multivariate polynomial interpolation / diversification polynomial / primitive root / discrete logarithm

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
QI Niuniu , TANG Min , DENG Guoqiang. Sparse Polynomial Interpolation Based on Diversification with High Probability. Journal of Systems Science and Mathematical Sciences, 2021, 41(12): 3324-3341 https://doi.org/10.12341/jssms21400

References

[1] Potts D, Tasche M. Nonlinear approximation by sums of nonincreasing exponentials. Applicable Analysis, 2011, 90(3):609-626.
[2] Pereyra V, Scherer G. Exponential Data Fitting and Its Application. Sherjah:Bentham Science Publishers, 2012.
[3] Javadi S M M, Monagan M. A sparse modular GCD algorithm for polynomials over algebraic function fields. Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2007, 187-194.
[4] Tang M, Yang Z F, Zeng Z B. Resultant elimination via implicit equation interpolation. Journal of Systems Science and Complexity, 2016, 29(5):1411-1435.
[5] Díaz A, Kaltofen E. On computing greatest common divisors with polynomials given by black boxes for their evaluations. Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, 1995, 232-239.
[6] Zippel R. Probabilistic algorithms for sparse polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1979, 216-226.
[7] Ben-Or M, Tiwari P. A deterministic algorithm for sparse multivariate polynomial interpolation. Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, 301-309.
[8] Ming-Deh, Huang A, Rao A J. Interpolation of sparse multivariate polynomials over large finite fields with applications. Journal of Algorithms, 1999, 33(2):204-228.
[9] Javadi S M M, Monagan M B. Parallel sparse polynomial interpolation over finite fields. Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, 2010, 160-168.
[10] Huang Q L. An improved early termination sparse interpolation algorithm for multivariate polynomial. Journal of Systems Science and Complexity, 2018, 31(2):539-551.
[11] Huang Q L. Sparse Polynomial interpolation over fields with large or zero characteristic. Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, ISSAC 2019, 219-226.
[12] Huang Q L, Gao X S. Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs. Journal of Symbolic Computation, 2019, 10:367-386.
[13] Huang Q L. Sparse polynomial interpolation based on diversification. Science China Mathematics, 2021, 1-16, DOI:10.1007/s11425-020-1791-5.
[14] Huang Q L, Gao X S. Revisit sparse polynomial interpolation based on randomized Kronecker substitution. Proceedings of the 21st International Workshop on Computer Algebra in Scientific Computing (CASC), 2019, 215-235.
[15] Josz C, Lasserre J B, Mourrain B. Sparse polynomial interpolation:Sparse recovery, superresolution, or prony? Advances in Computational Mathematics, 2019, 45(3):1401-1437.
[16] Kaltofen E L, Yang Z. Sparse multivariate function recovery with a small number of evaluations. Journal of Symbolic Computation, 2016, 75:209-218.
[17] Arnold A, Giesbrecht M, Roche D S. Faster sparse multivariate polynomial interpolation of straight-line Programs. Journal of Symbolic Computation, 2016, 75:4-24.
[18] Kunis S, Peter T, Roemer T, Ohe UVD. A multivariate generalization of Prony's method. Linear Algebra and Its Applications, 2016, 490:31-47.
[19] Roth I, Kliesch M, Flinth A, et al. Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements. IEEE Transactions on Signal Processing, 2020, 68:4002-4016.
[20] Hu J, Monagan M B. A fast parallel sparse polynomial GCD algorithm. Journal of Symbolic Computation, 2021, 105:28-63.
[21] Monagan M B, Tuncer B. Using sparse interpolation in Hensel lifting. Proceedings of the 18th International Workshop on Computer Algebra in Scientific Computing, 2016, 381-400.
[22] Cuyt A, Lee W S, Yang W. On tensor decomposition, sparse interpolation and Padé approximation. Jaen Journal on Approximation, 2016, 8(1):33-58.
[23] Castro Y D, Gamboa F, Henrion D, et al. Exact solutions to super resolution on semi-algebraic domains in higher dimensions. IEEE Transactions on Information Theory, 2017, 63(1):621-630.
[24] Monagan M B, Tuncer B. Using sparse interpolation to solve multivariate diophantine equations. ACM Communications in Computer Algebra, 2015, 49(3):94-97.
[25] Plonka G, Wannenwetsch K, Cuyt A, et al. Deterministic sparse FFT for M-sparse vectors. Numerical Algorithms, 2018, 78(1):133-159.
[26] Chen Y K, Chen X H, Wang Y F, et al. The interpolation of sparse geophysical data. Survey in Geophysics, 2019, 40(1):73-105.
[27] Hou Y, Cuyt A, Lee W S, et al. Decomposing textures using exponential analysis. Proceedings of the IEEE International Conference on Acoustics, 2021, 1920-1924.
[28] Cuyt A, Hou Y, Knaepkens F, et al. Sparse multidimensional exponential analysis with an application to radar imaging. SIAM Journal on Scientific Computing, 2020, 42(3):675-695.
[29] Giesbrecht M, Roche D S. Diversification improves interpolation. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, 2011, 123-130.
[30] Zippel R. Interpolating polynomials from their values. Journal of Symbolic Computation, 1990, 9(3):375-403.
PDF(668 KB)

268

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉