A new algorithm for sparse interpolation of multivariate polynomials

Citation

Cuyt A & Lee W (2008) A new algorithm for sparse interpolation of multivariate polynomials. Theoretical Computer Science, 409 (2), pp. 180-185. https://doi.org/10.1016/j.tcs.2008.09.002

Abstract
To reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables. Here we present a new technique, based on Rutishauser’s qd-algorithm, in which we overcome both drawbacks.

Keywords
Black box polynomial; Symbolic–numeric sparse interpolation; qd-algorithm; Generalized eigenvalue; Hadamard polynomial; Early termination

Journal
Theoretical Computer Science: Volume 409, Issue 2