Chunky and equal-spaced polynomial multiplication (Q540329)

A typical problem of computer algebra is addressed in this paper, namely the efficient multiplication of large polynomials. Here, a certain type of polynomials, called chunky, is considered, where there are chunks of nonvanishing coefficients near to each other (i.e., with similar powers or indices). This does not allow a worst-case analysis as is usual, but a new fairly efficient way to analyse the problem of multiplication. Algorithms are given for this new approach and it is proved that they are still of the same efficiency in the worst case as the previous methods, but are better in many other cases. (The first algorithm is about chunky multiplication, and the second algorithm about optimal chunk size computation.) The optimal chunk size is studied as well as the case when the coefficients of the polynomial are not chunky but are spaced at equal distances apart (again, from the exponent or index point of view; algorithms for equal-spaced multiplication and conversion).