# Modèles creux, calcul symbolique numérique et codes

13:00
Thursday
20
Nov
2014
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.

Planning :

14h00 - 15h00 :
Mark Giesbrecht (U Waterloo) : Sparsity, Complexity and Practicality in Symbolic Computation

15h30 - 16h30 :
Erich Kaltofen (NCSU) : Sparse Multivariate Rational Function Recovery With Many Errors in the Evaluations

# 1) Sparsity, Complexity and Practicality in Symbolic Computation

Mark Giesbrecht
Director, Cheriton School of Computer Science
University of Waterloo

Modern symbolic computation systems provide an expressive language for describing mathematical objects.  For example, we can easily enter equations such as

f=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+1

into a computer algebra system.  However, to determine the factorization

f -> (x^{2^{99}}y+y^{2^{99}}x+1)^2

with 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.

# 2) Sparse Multivariate Rational Function Recovery With Many Errors in the Evaluations

Erich Kaltofen,
ACM fellow,
Professor at North Carolina State University (NCSU), Math Dept,
Raleigh, NC. USA.

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).