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