Practical fast polynomial multiplication

ABSTRACT

The “fast” polynomial multiplication algorithms for dense univariate polynomials are those which are asymptotically faster than the classical O(N2) method. These “fast” algorithms suffer from a common defect that the size of the problem at which they start to be better than the classical method is quite large; so large, in fact that it is impractical to use them in an algebraic manipulation system. A number of techniques are discussed here for improving these fast algorithms. The combination of the best of these improvements results in a Hybrid Mixed Basis FFT multiplication algorithm which has a cross-over point at degree 25 and is generally faster than a basic FFT algorithm, while retaining the desirable O(N log N) timing function of an FFT approach. The application of these methods to multivariate polynomials is also discussed. The use is advocated of the Kronecker Trick to speed up a fast algorithm. This results in a method which has a cross-over point at degree 5 for bivariate polynomials. Both theoretical and empirical computing times are presented for all algorithms discussed.

REFERENCES

• 1: Agarwal R.C. and Burrus C.S.: Number Theoretic Transforms to Implement Fast Digital Convolution; IBM Research Report RC5025, 40 pp, (1974).
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Borodin A. and Moenck R.: Fast Modular Transforms; J. Computer and System Sciences, Vol 18, pp 366-387 (1974).
• 4: Cooley J.W. and Tukey J.W.: An Algorithm for Machine Calculation of Complex Fourier Series; Math. Comp., Vol 19, pp 297-301 (1965).
• 5: Fateman R.J.: Polynomial Multiplication, Powers and Asymptotic Analysis: Some Comments; SIAM J. of Computing, Vol 3, pp 196-213 (1974).
• 6: Gentleman W.M. and Sande G.: Fast Fourier Transforms - For Fun and Profit; Proc AFIPS 1966 FJCC, Vol 29, pp 563-578.
• 7: Gustavson F. and Yun D.: Arithmetic Complexity of Unordered Sparse Polynomials; preprint.
• 8: Andrew D. Hall, Jr., The Altran system for rational function manipulation — a survey, Communications of the ACM, v.14 n.8, p.517-521, Aug. 1971 [doi>10.1145/362637.362644]
• 9: Ellis Horowitz, A Sorting Algorithm for Polynomial Multiplication, Journal of the ACM (JACM), v.22 n.4, p.450-462, Oct. 1975 [doi>10.1145/321906.321908]
• 10: Johnson S.C.: Sparse Polynomial Arithmetic; Proc EuroSam 74 Conf, pp 63-71 (1974).
• 11: Kanada E. and Goto E.: A Hashing Method for Fast Polynomial Multiplication.
• 12: Karatsuba A.: Doklady Akademia Nauk SSSR, Vol 145, pp 293-294 (1962).
• 13: Knuth D.: Seminumerical Algorithms; Addison-Wesley, Reading, Mass (1962).
• 14: John D. Lipson, Chinese remainder and interpolation algorithms, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.372-391, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806309]
• 15: Robert Thomas Moenck, Studies in fast algebraic algorithms., 1973
• 16: Moenck R.: On the Efficiency of Algorithm for Polynomial Factoring; to appear in Math. Comp.
• 17: Moenck R.: Another Polynomial Homomorphism; to appear in Acta Informatica.
• 18: Pollard J.M.: The Fast Fourier Transform in a Finite Field; Math. Comp., Vol 25, No. 114, pp 365-374 (April 1971).
• 19: Richard C. Singleton, On computing the fast Fourier transform, Communications of the ACM, v.10 n.10, p.647-654, Oct. 1967 [doi>10.1145/363717.363771]
• 20: Strassen V.: Die Berechnungs Komplexitaete elementar symetrischen Funktionen und von interpolations Koeffizienten; Numerische Math., Vol. 20, pp 238-251 (1973).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General
      I.1.3 Languages and Systems

General Terms:
Algorithms, Theory