A Sorting Algorithm for Polynomial Multiplication
Ellis Horowitz · Journal of the ACM · 1975
ABS'rRACT Given two polynomials with n nonzero terms and t terms in the product, 2n -1 < t < n 2, it Is shown that the conventmnal polynomml multiphcatmn algorithm can take as many as ~9(n 3) operations.An alternate algorithm which does a binary merge-sort is given which has a worst-case bound of 0(n~log~n) exponent comparisons but may require 0(n *) storage A new algorithm, based upon a sorting strategy for the exponents, is given which behaves as O(n21og2n) and requires only ~)(t) storage Moreover, the algorithm works in hnear time for several Important special cases, namely for completely dense and completely sparse polynommls KEY "WORDS AND PHRASES polynomml multiphcation, sparse polynomml multiplication, sorting, tableau sorting CR ('ATEGORI~S" 5 25, 5 31, 5 7 1.Introductwn Suppose that we have two polynomials of degrees n -1, m -1, respectively,an-1 ~ O, andand we are interested in algorithms for computing their product.A and B above constitute the usual model for which multiplication algorithms have been analyzed.This model naturally yields bounds which are a function of the two degrees.For example, the classical pencil and paper multiplication method apphed to A and B takes 0(rnn) arithmetic operations But one must draw the distinction between polynomials as above and more generally ~n and ~ term polynomials.We will see later that the classical multiplication algorithm applied to polynomials of this latter type does not take O(mn) but O(m2n) arithmetic operations.From an asymptotic viewpoint there are better methods for multiplication.The current best relies on the use of the discrete fast Fourier transform and its convolution property (see Knuth [5, p. 269]).The time for this method is ~9(m log2m) assuming m ~_ n.However, this method is entirely insensitive to sparsity.This is clear from its first step, which is to consider the coefficients of A and B as elements of a k-tuple where k is the smallest power of 2 greater than or equal to m ..{-n -1.After the transform is applied all of the resulting elements will, in general, become nonzero.For polynomials as given above where all or most of the a,, b, are nonzero this technique can be quite effective.However, it will suffer badly when nn and n are large, but many of the coefficients are zero.For a system which is a general polynomial manipulator it makes sense to represent only the nonzero coefficients, and this is precisely what is done in almost all instances.This