Séminaire LJKModè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 blackbox polynomial will be assumed to have some error, and all numbers are represented in standard, fixedprecision, 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 BenOr & 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 Wenshin Lee and George Labahn.
