A fast, low-space algorithm for multiplying dense multivariate polynomials

ABSTRACT

This paper presents an improved adaptive hybrid algorithm for multiplying dense multivariate polynomials that is both time and space efficient. The hybrid algorithm makes use of two families of univariate algorithms, one Karatsuba based and the other DFT based, which are applied recursively to solve the multivariate problem. The hybrid algorithm is adaptive in that particular univariate algorithms are selected at run time to minimize the time complexity; an order-of-magnitude speedup with respect to classical multiplication is achieved over the entire practical range except for very small problems. Empirical investigation shows that most of the theoretical superiority is maintained in actual implementation. The largest contribution to the space requirements of the total algorithm is determined by the univariate algorithm used for the outermost variable; except for quite small problems, selecting univariate algorithms to minimize run time almost always leads to situations where the space requirements of the total algorithm are extremely close to the space required merely to store the result.

REFERENCES

• 1: AGARWAL, R. C., AND COOLEY, J.W. New algorithms for digital convolution. IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 5 (Oct. 1977), 392-410.
• 2: BONNEAU, R. J. Fast polynomial operations using the fast Fourier transform. Ph.D. thesis, Dept. of Mathematics, MIT, Cambridge, 1974 (unpublished).
• 3: Richard J. Fateman, A case study in interlanguage communication: Fast LISP polynomial operations written in 'C', Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.122-125, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806381]
• 4: FATEMAN, R.J. Polynomial multiplication, powers and asymptotic analysis: Some comments. SIAM J. Comput. 3, 3 (Sept. 1974), 196-213.
• 5: Joseph H. McClellen , Charles M. Rader, Number Theory in Digital Signal Processing, Prentice Hall Professional Technical Reference, 1979
• 6: Robert T. Moenck, Practical fast polynomial multiplication, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.136-148, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806332]
• 7: MOENCK, R.T. Another polynomial homomorphism. Acta Inf. 6 (1976}, 153-169.
• 8: David K. Probst , Vangalur S. Alagar, An Adaptive Hybrid Algorithm for Multiplying Dense Polynomials, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.16-23, April 05-07, 1982
• 9: WINOGRAD, S. On computing the discrete Fourier transform. Math. Comput. 32, 141 (Jan. 1978), 175-199.
• 10: WINOGRAD, S. Arithmetic Complexity of Computations. SIAM, Philadelphia, 1980.

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms; Algebraic algorithms

General Terms:
Algorithms, Design