New Algorithms for Polynomial Multiplication
Dorothea A. Klip · SIAM Journal on Computing · 1979
Exploiting the structure of the 2-dimensional sorting problem associated with the polynomial product has been the strategy in the design of certain algorithms which are faster for a large class of problems than those found in the literature. First a parallel is drawn between GEN–MULT and Horowitz’s SORT–MULT algorithm [A sorting algorithm for polynomial multiplication, J. Assoc. Comput. Mach., 22 (1975), pp. 450–462]. The former owes its better performance to the global incorporation of the structure. A geometric picture of the relative location of the product exponents enabled us to present a new approach, implemented by the SLICE algorithms, in which the product exponents are sorted in separate parallel slices. For a class of problems of moderate size and sparsity, which was investigated by Johnson [Sparse polynomial arithmetic, Proc. Eurosam Conf., SIGSAM Bull., 8 (1974), pp. 63–71] with the ALTRAN system, the simple SLICE–S algorithm gave a 1:4 improvement, timewise and relative to sorting effort, as compared with ALTRAN’s LI algorithm. The optimized version, for large, sparse problems, is based on theoretical arguments. It performs in linear time as an average with respect to its major operations.