Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Winter 2008/2009 

Some New Algorithms for Sparse Polynomials

Mark Giesbrecht  (University of Waterloo, Canada)

Tuesday  31 March 2009, 15.00, b-it  1.25 (cosec meeting room)

We present new algorithms for some basic computations with sparse, or
lacunary, polynomials. First we examine the problem of sparsest-shift
interpolation -- finding a shifted power basis in which a polynomial
is sparsest and interpolating in that basis. We then consider
detecting when a sparse polynomial is a perfect power of another
polynomial, and if so, computing the polynomial "root". These
algorithms require a time which is polynomial in the size of the
sparse representation of the input and output.

This is joint work with Daniel S. Roche

Imprint, webmaster & more