Computing with polynomials given by straight-line programs I: greatest common divisors

ABSTRACT

We develop algorithms on multivariate polynomials represented by straight-line programs for the greatest common divisor problem and conversion to sparse representation. Our algorithms are in random polynomial-time for the usual coefficient fields and output with controllably high probability the correct result which for the GCD problem is a straight-line program determining the GCD of the inputs and for the conversion algorithm is the sparse representation of the input. The algorithms only require an a priori bound for the total degrees of the inputs. Over rational numbers the conversion algorithm also needs a bound on the size of the polynomial coefficients. As specializations we get, e.g., random polynomial-time algorithms for computing the sparse GCD of polynomial determinants or for computing the sparse solution of a linear system whose coefficients are given by formulas.

REFERENCES

• BaSt83: W. Baur and V. Strassen, "The ,:ompl0xity of partial derivatives,'' TheoretieM Comp. ,%i.. vol. 22, pp. 317-~30. 1983.
• Br71: 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]
• Ga83: J. ,,'on zur Gathen. "Factoring sparse multivariate polynomiab." Proc. ~4tb IE~~ Syrup Foundations Comp..eel.. pp. 172-179, 1983.
• Ga85: Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]
• Moe73: R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
• MoYu73: Joel Moses , David Y. Y. Yun, The EZ GCD algorithm, Proceedings of the annual conference, p.159-166, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805698]
• Pl77: D. A. Plaisled, "Sparse complex polynomials and polynomial reducibility." d. Comp. System Sei., vol. 14. pp. 210-221, 1977.
• Ra80: M. Rabin. "Probabilistic algorithms for testing primality." J. Number Th~orp, vol. 12, pp. 128-138. 1980.
• Sch77: A. Sch~,nhag,,. ",qchnelle Multiplikation yon Polynomen ilb,'r KSrpern der Charakteristik 2," Acts Inf., vol. 7. pp. 39.5-398. 1977.
• Sch80: A. Schdnhage, "Storage modification routines," SI.4M d. Comp., vol. c~. pp. 490-508, 1980.
• Schw80: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• Stou84: D. R. Stoutemyer, "Which polynomial representation is best?," Third MACSYMA Users' Conference. pp, 221-243, General Electric, 1984.
• St72: V. Strsasett, "Berechnung und Programm." Acta Inf.. vol. 1, pp. S20-835, 1972.
• St73: V. Strassen, "Vermeidung von Divisionen," J. reine u. angew. Math., vol. 264, pp. 182-202. 1973.
• VSBR83: L. Valiant, S. Skyum, S. Berkowitz. and C. Rackoff. "Fast parallel computation of polynomials using few processors," SIAM d. Comp., vol. 12, pp. 641-644, 1985.
• Zi79: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• Co67: 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]
• Kn81: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Ku74: H. T. Kung, "On computing reciprocals of power series." Numer. Math., vol. 22, pp. 341-348, 1974.
• RoSch62: J. B. Rosser and L. Schoenfeld. ;'Approximate formulas of some functions of prime numbers," {lliniot J. Math.. voi 6, pp. 64-94. 1962.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

General Terms:
Algorithms, Theory, Verification