We consider the problem of interpolating a multivariate polynomial that is given as a black box. When the target polynomial is sparse, where much fewer non-zero terms exist, there are efficient interpolation algorithms that take advantage of such situation, such as Zippel's algorithm, the Ben-Or/Tiwari algorithm, and their variances. However, these methods are developed for exact arithmetic.
In this talk, I will discuss general issues and a framework for sparse interpolation of a black-box polynomial in a floating-point environment. That is, both the inputs and outputs of the black box are precise up to a fixed number of digits. Due to our observation of the link between the exact Ben-Or/Tiwari sparse interpolation and the classical Prony's method for interpolating a sum of exponential functions, we explore recent development in the Prony's method. Our approaches for floating-point sparse polynomial interpolation and possible extensions will be addressed.
This is a joint work with Mark Giesbrecht and George Labahn at University of Waterloo, Canada.