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