Symbolic Computation Group

Finding fast algorithms to compute the product of two polynomials has been a major focus of computer algebra research over the past 50 years. However, most previous results seem to concentrate only on the worst-case complexity in terms of the size of the input polynomials. This coarse analysis overlooks many "easy" cases when the computation can in fact be performed much more quickly. We apply the technique of adaptive analysis to develop algorithms which perform better in many cases, but which are still never (asymptotically) worse than the current state of the art. In addition to a finer-grained analysis, these new algorithms also provide in some sense a gradient between dense and sparse multiplication techniques. Three ideas for adaptive polynomial multiplication are given, and one is investigated more deeply with an implementation and timing comparisons.