Article

A new algorithm for sparse interpolation of multivariate polynomials

Details

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

StatusPublished
FundersUniversity of Antwerp
Publication date17/12/2008
Publication date online06/09/2008
Date accepted by journal19/05/2008
URLhttp://hdl.handle.net/1893/29005
ISSN0304-3975

People (1)

People

Dr Wen-shin Lee

Dr Wen-shin Lee

Lecturer, Computing Science and Mathematics - Division