Parallel univariate polynomial factorization on shared-memory multiprocessors

ABSTRACT

Using parallelism afforded by shared-memory multiprocessors to speed up systems for polynomial factorization is discussed. The approach is to take the fastest known factoring algorithm for practical purposes and parallelize key parts of it. The univariate factoring algorithm consists of two major tasks (a) factoring modulo small integer primes and (b) EEZ lifting and recovery of true factors. A C coded system PFACTOR that implements (a) in parallel is described in detail. PFACTOR is a stand-alone parallel factorizer that can take input from a file, a pipe or a socket connection over a network. It can also be used interactively as a UNIX command. PFACTOR consists of parallel selection of primes, automatic balancing of work, parallel Berlekamp algorithm, and parallel reconciliation of degrees of factors modulo different primes. Actual timings on the Encore Multimax show the effectiveness of the approach. Work on part (b) is still on going.

REFERENCES

• 1: E. R. Berlekamp, "Factoring Polynomials over Finite Fields," Bell System Tech. J., V. 46, 1967, pp. 1853- 1859. Kingston Polytechnic, Kingston, England, Mar. 28-30, 1983.
• 2: D. Cantor and H. Zassenhaus, "A New Algorithm for Factoring Polynomials over Finite .Fields," Math. Comp., 36 (1981), pp. 587-592.
• 3: Jean Della Dora , John Fitch, Computer Algebra and Parallelism, Academic Press, Inc., Orlando, FL, 1989
• 4: S. C. Johnson , R. L. Graham, Problem #7, ACM SIGSAM Bulletin, v.8 n.1, p.4-4, February 1974 [doi>10.1145/1086823.1086825]
• 5: E. KaItofen, "Factorization of Polynomials," Computer Algebra-Symbolic and Algebraic Computation, Computing, Suppl. 4, Springer-Verlag, 1982, pp. 95- 113.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: A. Lenstra, H. Lenstra and L. Lovasz, "Factoring Polynomials with Rational Coefficients," Math. Ann., Vol. 261, 1982, pp. 515~534.
• 8: P. M. A. Moore , A. C. Norman, Implementing a polynomial factorization and GCD package, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.109-116, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806379]
• 9: David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
• 10: David R. Musser, On the Efficiency of a Polynomial Irreducibility Test, Journal of the ACM (JACM), v.25 n.2, p.271-282, April 1978 [doi>10.1145/322063.322071]
• 11: B. D. Saunders , H. R. Lee , S. K. Abdali, A parallel implementation of the cylindrical algebraic decomposition algorithm, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.298-307, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74576]
• 12: P. S. Wang, "An Improved Multivariate Polynomial Factoring Algorithm," Mathematics of Computation, Vol. 32, No. 144, Oct. 1978, pp. 1215-1231.
• 13: P. S. Wang and B. M. Trager, "New Algorithms for Polynomial Square-free Decomposition over the Integers,'' SIAM J. Computing, Vol. 8, No. 3, Aug. 1979, pp. 300-305.
• 14: P. S. Wang, "Parallel p-adic Constructions in the Univariate Polynomial Factoring Algorithm," Proceedings, MACSYMA Users' Conference 1979, Cambridge, MA, MIT pp. 310-318.
• 15: P. S. Wang, "Factoring Multivariate Polynomials over Algebraic Number Fields," math. comp., vol 30, Apr. 1976, pp. 324-336.
• 16: Paul S. Wang, Early detection of true factors in univariate polynominal factorization, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.225-235, March 28-30, 1983
• 17: P. S. Wang and K. Weber, "Guide to Parallel Programming on the Encore Multimax," Technical Report (CS-8901-03), Dept. Math and C.S., Kent State University, Kent, OH, 44242 USA.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

General Terms:
Algorithms, Performance