Output-sensitive sparse polynomial multiplication via interpolation.

Andrew Arnold, North Carolina State University

Wednesday July 13th, K9509, 1:30pm.

Abstract

A sparse representation of a polynomial F is a list comprised of its
nonzero terms.  We consider polynomial multiplication with integer
coefficients, where the inputs and output are all in a sparse
representation.  To our knowledge, any known algorithm for this problem has
a time cost factor that is quadratic in the combined bit size of the inputs
and outputs.  In this talk we present a probabilistic Monte Carlo algorithm
for computing a sparse polynomial product, that reduces (but does not
remove), this quadratic cost factor.  This algorithm relies on techniques
from sparse interpolation, and is joint work with Daniel S. Roche (ISSAC,
2015).  A challenge of removing this aforementioned quadratic factor is
that the size of the output is initially unknown, given the inputs.
Lastly, we will show a subtle error in the original cost analysis of the
algorithm, and how this may be repaired using the technique of early
termination (Kaltofen and Lee, JSC, 2003).