Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs. (November 2020)

• Record Type: Journal Article
• Authors: Huang, Qiao-Long; Gao, Xiao-Shan
• Is Part Of: Journal of symbolic computation. Volume 101(2020)
• Page Start: 367
• Page End: 386
• Publication Date: 2020-11
• Subjects: 00-01 -- 99-00; Black box -- Interpolation -- Kronecker substitution; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2019.10.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let f be an n -variate polynomial given by a straight-line program, which has a total degree bound D and a term bound T . Our deterministic algorithm is quadratic in n, T and cubic in log ⁡ D in the Soft-Oh sense, which has better complexities than existing deterministic interpolation algorithms in most cases. Our Monte Carlo interpolation algorithms have better complexities than existing Monte Carlo interpolation algorithms and are the first algorithms whose complexities are linear in nT and polynomial in log ⁡ D in the Soft-Oh sense.