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 under various reasonable assumptions, or are 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 both traditional" exact and symbolic domains, such as the integers and finite fields, as well as approximate (floating point) data, will be considered.