Greatest common divisors of polynomials given by straight-line programs

ABSTRACT

Algorithms on multivariate polynomials represented by straight-line programs are developed. First, it is shown that most algebraic algorithms can be probabilistically applied to data that are given by a straight-line computation. Testing such rational numeric data for zero, for instance, is facilitated by random evaluations modulo random prime numbers. Then, auxiliary algorithms that determine the coefficients of a multivariate polynomial in a single variable are constructed. The first main result is an algorithm that produces the greatest common divisor of the input polynomials, all in straight-line representation. The second result shows how to find a straight-line program for the reduced numerator and denominator from one for the corresponding rational function. Both the algorithm for that construction and the greatest common divisor algorithm are in random polynomial time for the usual coefficient fields and output a straight-line program, which with controllably high probability correctly determines the requested answer. The running times are polynomial functions in the binary input size, the input degrees as unary numbers, and the logarithm of the inverse of the failure probability. The algorithm for straight-line programs for the numerators and denominators of rational functions implies that every degree-bounded rational function can be computed fast in parallel, that is, in polynomial size and polylogarithmic depth.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Ano, A. V., STEIGLrrz, K., AND ULLMAN, J.D. Evaluating polynomials at fixed sets of points. SIAM J. Comput. 4 (1975), 533-539.
• 3: BAUR, W., AND STRASSEN, V. The complexity of partial derivatives. Theoret. Comput. Sci. 22 (1983), 317-330.
• 4: BRENT, R. P., GUSTAVSON, F. G., AND YUN, D. Y. Y. Fast solution of Toeplitz systems of quations and computation of Pad6 approximants. J. Algorithms 1 (1980), 259-295.
• 5: 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]
• 6: BtmCH, J. R., AND HoPcRoFr, J. E. Triangular factorization and inversion by fast matrix multiplication. Math. Comput. 28 (1974), 231-236.
• 7: Bruce W. Char , Keith O. Geddes , Gaston H. Gonnet, GCDHEU: Heuristic Polynomial GCD Algorithm Based on Integer GCD Computation, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.285-296, July 09-11, 1984
• 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: Stephen R. Czapor , Keith O. Geddes, A Comparison of Algorithms for the Symbolic Computation of Padé Approximants, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.248-259, July 09-11, 1984
• 10: T. Freeman , G. Imirzian , E. Kaltofen, A system for manipulating polynomials given by straight-line programs, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.169-175, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32473]
• 11: 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]
• 12: J von zur Gathen, Parallel arithmetic computations: a survey, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, p.93-112, June 1986, Bratislava, Czechoslovakia
• 13: Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
• 14: HARDY, G. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers. Oxford University Press, Oxford, England, 1979.
• 15: J Heintz, On polynomials with symmetric Galois group which are easy to compute, Theoretical Computer Science, v.47 n.1, p.99-105, Nov. 1986
• 16: HWINTZ, J., AND SCHNORR, C.P. Testing polynomials which are easy to compute, in Monographie de L'Enseignement Math~matique, vol. 30. Imprimerie Kundig, Gen~ve, Switzerland, 1982, pp. 237-254.
• 17: HYAFIL, L. On the parallel evaluation of multivariate polynomials. SIAM J. Comput. 8 (1979), 120-123.
• 18: Oscar H. Ibarra , Shlomo Moran, Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs, Journal of the ACM (JACM), v.30 n.1, p.217-228, Jan. 1983 [doi>10.1145/322358.322373]
• 19: IBARRA, O. H., MORAN, S., AND ROSIER, L.E. Probabilistic algorithms and straight-line programs for some rank decision problems. Inf. Process. Lett. 12 (1981), 227-232.
• 20: Richard D. Jenks, A Primer: 11 Keys to New Scratchpad, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.123-147, July 09-11, 1984
• 21: E Kaltofen, Computing with polynomials given by straight-line programs I: greatest common divisors, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.131-142, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22160]
• 22: KAL~OFEN, E. Computing with polynomials given by straight-line programs. II. Sparse factorization. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985, pp. 451-458.
• 23: IC~LTOFEN, E. Factorization of polynomials given by straight-line programs. In Randomness in Computation: Advances in Computing Research, S. Micali, Ed. JAI Press, Greenwich, Conn., Jan. 1987.
• 24: E Kaltofen, Uniform closure properties of P-computable functions, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.330-337, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12163]
• 25: E. Kaltofen, Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.443-452, January 1987, New York, New York, United States [doi>10.1145/28395.28443]
• 26: Erich Kaltofen , Heinrich Rolletschek, Arithmetic in Quadratic Fields with Unique Factorization, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.279-288, April 01-03, 1985
• 27: KNUTH, D.E. The analysis of algorithms. Actes du congrbs international des Math~maticiens 3 (1970), 269-274.
• 28: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 29: KRISHNAMURTHY, E. V., RAO, T. M., AND SUBRAMANIAN, K. Finite segment p-adic number systems with applications to exact computation. Proc. Indian Acad. Sci. 81, sec. A, 2 (1975), 58-79.
• 30: KUNG, H.T. On computing reciprocals of power series. Numer. Math. 22 (1974), 341-348.
• 31: G L Miller , V Ramachandran , E Kaltofen, Efficient parallel evaluation of straight-line code and arithmetic circuits, Proc. of the Aegean workshop on computing on VLSI algorithms and architectures, p.236-245, August 1986, Loutraki, Greece
• 32: MILLER, G. F., AND REIF, J.H. Parallel tree contraction and its application, in Proceedings of the 26th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985, pp. 478-489.
• 33: 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]
• 34: 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]
• 35: PLAISTED, D.A. Sparse complex polynomials and polynomial reducibility. J. Comput. Syst. Sci. 14 (1977), pp. 210-221.
• 36: RossEa, J. B., AND SCHOENFELD, L. Approximate formulas of some functions of prime numbers. 111. J. Math. 6 (1962), 64-94.
• 37: 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]
• 38: SCrIONHAGE, A. Schnelle Kettenbruchentwicklungen. Acta inf. 1 (1971), 139-144 (in German).
• 39: SCHOm-L~,GE, A. Schnelle Multiplikation von Polynomen fiber Ktrpern der Charakteristik 2. Acta Inf. 7 (1977), 395-398 (in German).
• 40: SOLOVAY, R. M., AND STRASSErq, V. A fast Monte-Carlo test for primality. SIAM J. Comput. 6{ (1977), 84-85. Correction: 7 (1978), 118.
• 41: STOUTEMEYER, D. R. Which polynomial representation is best? In Proceedings of the 3rd MACSYMA Users'Conference, General Electric, Schenectady, N.Y., 1984, pp. 221-243.
• 42: STRASSEN, V. Berechnung und Programm I. Acta Inf. 1 (1972), 320-335 (in German).{
• 43: STrtASSEN, V. Vermeidung von Divisionen. J. Reine u. Angew. Math. 264 (1973), 182-202 (in German).
• 44: VALIANT, L. The complexity of computing the permanent. Theoret. Comput. Sci. 8 (1979), 189-201.
• 45: VALIANT, L. Reducibility by algebraic projections. L'Enseignement Math. 28 (1982), 253-268.
• 46: VALIANT, L., SKYUM, S., BERKOWITZ, S., AND RACKOFF, C. Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12 ( 1983), 641-644.
• 47: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

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

General Terms:
Algorithms, Design, Theory, Verification