Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials

ABSTRACT

Three theorems are presented that establish polynomial straight-line complexity for certain operations on polynomials given by straight-line programs of unbounded input degree. The first theorem shows how to compute a higher order partial derivative in a single variable. The other two theorems impose the degree of the output polynomial as a parameter of the length of the output program. First it is shown that if a straight-line program computes an arbitrary power of a multivariate polynomial, that polynomial also admits a polynomial bounded straight-line computation. Second, any factor of a multivariate polynomial given by a division-free straight-line program with relatively prime co-factor also admits a straight-line computation of length polynomial in the input length and the degree of the factor. This result is based on a new Hensel lifting process, one where only one factor image is lifted back to the original factor. As an application we get that the greatest common divisor of polynomials given by a division-free straight-line program has polynomial straight-line complexity in terms of the input length and its own degree.

REFERENCES

• 1: W. Baur and V. Strassen, "The complexity of partial derivatives," Theoretical Comp. Sci., vol. 22, pp. 317- 330, 1983.
• 2: R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun, "Fast solution of Toeplitz systems of equations and computation of Padd approximants," J. AIqorithrns, vol. 1, pp. 259-295, 1980.
• 3: 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]
• 4: D. G. Cantor and E. Kaltofen, "Fast multiplication of polynomials with coefficients from an arbitrary ring," Manuscript, March 1987.
• 5: 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]
• 6: 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]
• 7: E. Kaltofen, "Factorization of polynomials given by straight-line programs," Math. Sei. Research Inst. Preprint, vol. 02018-86, Berkeley, CA, 1986. To appear in: "Randomness in Computation," Advance8 in Computing Research, S. Micali ed.., JAI Press Inc., Greenwich, CT, January 1987.
• 8: 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]
• 9: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: 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
• 11: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• 12: 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]
• 13: 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]
• 14: A. $ch~nhage, "Schnelle Multiplikation yon Polynomen fiber Kgrpern der Charakteristik 2," A eta inf., vol. 7, pp. 39,5-398, 1977. (In German).
• 15: V. Strassen, "Berechnung und Programm I," Acts inf., vol. 1, pp. 320-335, 1972. (In German).
• 16: V. Strassen, "Ve' meidung yon Divisionen," d. reine u. angew. Math., vol. 264, pp. 182-202, 1973. (In GermEtrl).
• 17: V. Strassen, "Algebraische Berechnungskomplexitltt," in Anniversary of Oberwolfach 198,~, Perspectives in Mathematics, pp. 509-550, Birkh/iuser Verlag, Basel, 1984. (In German).
• 18: L. Valiant, "Reducibility by algebraic projections," L'Ensei#ner~.,ent math~matique, vol. 28, pp. 253-268. 1982.
• 19: L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, "Fast parallel computation of polynomials using few processors," SIAM J. Comp., vol. 12, pp. 641-644, 1983.
• 20: Paul S. Wang, The EEZ-GCD algorithm, ACM SIGSAM Bulletin, v.14 n.2, p.50-60, May 1980 [doi>10.1145/1089220.1089228]
• 21: D. Y. Y. Yun, "The Hensel lemma in algebraic manipulation,'' Ph.D. Thesis, M.I.T., 1974. Reprint: Garland Publ., New York 1980.
• 22: H. Zassenhaus, "On Hensel factorization I," d. Number Theory, vol. 1, pp. 291-311, 1969.

INDEX TERMS

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Theory, Verification