Faster sparse multivariate polynomial interpolation of straight-line programs. (July 2016)

• Record Type: Journal Article
• Authors: Arnold, Andrew; Giesbrecht, Mark; Roche, Daniel S.
• Is Part Of: Journal of symbolic computation. Volume 75(2016)
• Page Start: 4
• Page End: 24
• Publication Date: 2016-07
• Subjects: Sparse interpolation -- Complexity -- Randomized algorithms -- Straight-line program; 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.2015.11.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Given a straight-line program whose output is a polynomial function of the inputs, we present a new algorithm to compute a concise representation of that unknown function. Our algorithm can handle any case where the unknown function is a multivariate polynomial, with coefficients in an arbitrary finite field, and with a reasonable number of nonzero terms but possibly very large degree. It is competitive with previously known sparse interpolation algorithms that work over an arbitrary finite field, and provides an improvement when there are a large number of variables.