Sparse polynomial interpolation based on derivatives. (January 2023)

• Record Type: Journal Article
• Authors: Huang, Qiao-Long
• Is Part Of: Journal of symbolic computation. Volume 114(2023)
• Page Start: 359
• Page End: 375
• Publication Date: 2023-01
• Subjects: Sparse polynomials -- Straight-line program -- Derivatives; 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.2022.06.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program (SLP). Both of our algorithms work over any finite fields F q with large characteristic. The first algorithm is randomized of the Monte Carlo type. Its bit complexity is linear in the number of non-zero terms T and the number of variables n of f . Let D be the partial degree bound of f . If q is in O ( ( n T D ) ( 1 ) ), our algorithm has better complexity than other existing algorithms. The second algorithm is deterministic; it has better complexity than any existing deterministic algorithms in the field with large characteristic. Its bit complexity is quadratic in n, T, log ⁡ D .