13:00

Thursday

20

Nov

2014

- Seminar

Place:

Organized by:

Clément Pernet

Speaker:

Mark Giesbrecht (U Waterloo) & Erich Kaltofen (NCSU)

Teams:

**Lieu** :

ENSIMAG Amphi H (rez de chaussé du bâtiment H, en face du bâtiment principal), rue de la passerelle, Domaine Universitaire, Saint Martin d'Hères.

14h00 - 15h00 :

15h30 - 16h30 :

Modern symbolic computation systems provide an expressive language for describing mathematical objects. For example, we can easily enter equations such asf=x^{2^{100}}y^2 + 2x^{2^{99}+1}y^{2^{99}+1}+2x^{2^{99}}y+y^{2^{100}}x^{2}+2y^{2^{99}}x+1into a computer algebra system. However, to determine the factorizationf -> (x^{2^{99}}y+y^{2^{99}}x+1)^2with traditional methods would incur huge expression swell and high complexity. Indeed, many problems related to this one are provably intractable, or suspected to be so. Nonetheless, recent work has yielded exciting new algorithms for computing with sparse mathematical expressions. In this talk, we will attempt to navigate this hazardous computational terrain of sparse algebraic computation. We will discuss new algorithms for sparse polynomial root finding and functional decomposition. We will also look at the ``inverse'' problem of interpolating or reconstructing sparse mathematical functions from a small number of sample points. Computations over traditional symbolic domains, such as the integers and finite fields, as well as symbolic-numeric computations for approximate (floating point) data, will be considered. Fast algorithms should require time polynomial in the size of the \emph{sparse} representation of the input and output, and will need to manage coefficient growth, intermediate expression swell, and numerical stability as appropriate to the problem.

Error-correcting decoding is generalized to multivariate sparse polynomial and rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (``outliers'').Our multivariate polynomial and rational function interpolation algorithm combines Zippel's symbolic sparse polynomial interpolation technique [Ph.D. Thesis MIT 1979] with the numeric algorithm by Kaltofen, Yang, and Zhi [Proc. SNC 2007], and removes outliers (``cleans up data'') by techniques from the Berlekamp/Welch decoder for Reed-Solomon codes. Our algorithm can correct to an error rate as high as 1/3.Our algorithms can build a sparse function model from a number of evaluations that is linear in the sparsity of the model, assuming a constant number of ouliers.This is joint work with Zhengfeng Yang (ECNU, Shanghai).