Séminaire LJK-Modèles et Algorithmes Déterministes: CASYS

 

Le Jeudi 6 Avril 2006 à 9h45 en Salle 1 - Tour IRMA

 

Séminaire de

 

Interpolation of Sparse Approximate Polynomials

 

Résumé:

 

Interpolation of polynomials is a fundamentally important problem in both numerical and algebraic computing, and has been very well studied for its mathematical properties. However, multivariate polynomials can get very large, even at relatively low degrees, when the number of variables is even modest. Exploiting sparsity is a key to computing efficiently with them.
Hence, we consider the problem of sparse interpolation of approximate
multivariate polynomials. We work in the "black box" model, wherein we can evaluate the polynomial at any point, but have no information as to how the values of the polynomials are determined. Both the inputs and outputs of the black-box polynomial will be assumed to have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic.

By interpolating the polynomials evaluated at random primitive roots of unity, we give efficient and provably numerically robust solutions.
We note the similarity between the exact Ben-Or & Tiwari sparse interpolation algorithm and the classical Prony's method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony's method. We look at the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected numerical conditioning achieved through randomization.

This is joint work with Wen-shin Lee and George Labahn.