Chunky and equal-spaced polynomial multiplication

Finding the product of two polynomials is an essential and basic prob-lem in computer algebra. While most previous results have focused on the worst-case complexity, we instead employ the technique of adaptive analysis to give an improvement in many “easy ” cases. We present two adaptive measures and methods for polynomial multiplication, and also show how to effectively combine them to gain both advantages. One use-ful feature of these algorithms is that they essentially provide a gradient between existing “sparse ” and “dense ” methods. We prove that these ap-proaches provide significant improvements in many cases but in the worst case are still comparable to the fastest existing algorithms.