Parallelization of the sparse modular GCD algorithm for multivariate polynomials on shared memory multiprocessors

ABSTRACT

Reported are experiences and practical results from parallelizing the modular GCD algorithm for sparse multivariate polynomials. The strategy is to identify key computation steps in the sequential algorithm and implement them in parallel. The two major steps of the sequential algorithm—computing the GCD modulo several primes and applying the Chinese Remainder Algorithm on the integer coefficients—are easily partitioned into independent subtasks. The subtask of computing the GCD modulo one prime can be subdivided further. Several parallel strategies for the multivariate GCD modulo a prime are presented. Actual timings on a Sequent Balance with 26 processors are presented.

REFERENCES

• 1: A. Akritas, Elements of computer algebra with applications, John Wiley & Sons, Inc., New York, NY, 1989
• 2: Balance Technical Summary. Sequent Computer Systems, Inc., 1986.
• 3: Batut, C., Bernardi, D., Cohen. It., Olivier, M. U~er'~ Guide to PARI.GP. Feb. 1991.
• 4: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 5: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 6: B. F. Caviness, Computer Algebra: Past and Future, Invited Lectures from the European Conference on Computer Algebra-Volume I, p.1-18, April 01-03, 1985
• 7: Bruce W. Char , Keith O. Geddes , Gaston H. Gonnet, GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation, Journal of Symbolic Computation, v.7 n.1, p.31-48, Jan. 1989 [doi>10.1016/S0747-7171(89)80004-5]
• 8: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 9: Collins, G., Encarnacion, M., Krandick, W., and Neubacher, A. A SA CLIB Primer.
• 10: Jean Della Dora , John Fitch, Computer Algebra and Parallelism, Academic Press, Inc., Orlando, FL, 1989
• 11: Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
• 12: Laure, M. Computing by Homomorphic Images. Computer Algebra Symbolic and Algebraic Computation, Loos R., Collins, G., Buchberger (eds). Pages 139- 168. Springer-Verlag. 1982.
• 13: Loos, R. Generalized Polynomial Remainder Sequence. Computer Algebra Symbolic and Algebraic Computation, Loos R., Collins, G., Buchberger (eds). Pages 115-137. Springer-Verlag. 1982.
• 14: Mathematics and Computer Science Division. Balance 8000/~1000 C Compiler User's Manual. Argonne National Laboratory, 1989.
• 15: Mathematics and Computer Science Division. Sequent Guide to Parallel Programming. Aragone National Laboratory, 1989.
• 16: Mignotte, M. An inequality about.factors of polynomials. Math. Comp., Vol. 28, 1974. Pages 1153-1157.
• 17: Carl Glen Ponder, Evaluation of "performance enhancements" in algebraic manipulation systems, 1988
• 18: Sequent Computer Systems. DYNIX programmer's Manual 1987.
• 19: Anita Osterhaug, Guide to parallel programming on Sequent computer systems: 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 20: Shreekant Thakkar , Paul Gifford , Gary Fielland, The Balance Multiprocessor System, IEEE Micro, v.8 n.1, p.57-69, January 1988 [doi>10.1109/40.521]
• 21: Villard, G. Chinese Remaindering on a MIMD Parallel Computer. Preprint Nov. 1990.
• 22: Wang, P. A Guide to Parallel Programming on the Sequent Balance, Technical Report, Institute for Mathematical Computation, Dept. of Math. and Comp. Sci., Kent State University, 1989.
• 23: P. S. Wang, Parallel univariate polynomial factorization on shared-memory multiprocessors, Proceedings of the international symposium on Symbolic and algebraic computation, p.145-151, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96915]
• 24: Paul S. Wang, Parallel univariate p-adic lifting on shared-memory multiprocessors, Papers from the international symposium on Symbolic and algebraic computation, p.168-176, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143304]
• 25: Zippel, Richard. Probabilistic Algorithms .for Sparse Polynomials. PhD. Thesis, Massachusetts Institute of Technology, 1979.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing); Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms