1) Sparsity, Complexity and Practicality in Symbolic Computation

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.