Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Hensel and Newton methods in valuation rings

Author: Joachim von zur Gathen
Journal: Math. Comp. 42 (1984), 637-661
MSC: Primary 12J20; Secondary 65P05
MathSciNet review: 736459
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We give a computational description of Hensel's method for lifting approximate factorizations of polynomials. The general setting of valuation rings provides the framework for this and the other results of the paper. We describe a Newton method for solving algebraic and differential equations. Finally, we discuss a fast algorithm for factoring polynomials via computing short vectors in modules.

References [Enhancements On Off] (What's this?)

  • [E] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 0219231
  • [N] Bourbaki, Eléments de Mathématiques, Livre II: Algèbre, Hermann, Paris, 1958.
  • [W] W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. Assoc. Comput. Mach. 18 (1971), 478–504. MR 0307450
  • [A] A. L. Chistov, Calculation of the Galois group over a function field of characteristic zero with an algebraically closed constant field in polynomial time, Mathematical methods for constructing and analyzing algorithms (Russian), “Nauka” Leningrad. Otdel., Leningrad, 1990, pp. 200–232, 237 (Russian). MR 1082380
  • [G] George E. Collins, Subresultants and reduced polynomial remainder sequences, J. Assoc. Comput. Mach. 14 (1967), 128–142. MR 0215512
  • [A] Fellmann, Newton-Iteration über nicht-archimedisch bewerteten vollständigen Ringen, Diplomarbeit, Zürich, 1977.
  • [K] K. O. Friedrichs, Symmetric positive linear differential equations, Comm. Pure Appl. Math. 11 (1958), 333–418. MR 0100718
  • [A] A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London. Ser. A. 248 (1956), 407–432. MR 0074349
  • [J] von zur Gathen, Factoring Sparse Multivariate Polynomials, Proc. 24th Annual IEEE Sympos. Foundations of Computer Science, Tucson, 1983, pp. 172-179.
  • [J] J. von zur Gathen and E. Kaltofen, Polynomial-time factorization of multivariate polynomials over finite fields, Automata, languages and programming (Barcelona, 1983) Lecture Notes in Comput. Sci., vol. 154, Springer, Berlin, 1983, pp. 250–263. MR 727661, 10.1007/BFb0036913
  • [E] Erich Kaltofen, A polynomial-time reduction from bivariate to univariate integral polynomial factorization, 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982) IEEE, New York, 1982, pp. 57–64. MR 780381
  • [E] Erich Kaltofen, Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput. 14 (1985), no. 2, 469–489. MR 784750, 10.1137/0214035
  • [D] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • [H] H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341–348. MR 0351045
  • [S] Landau, Factoring Polynomials Over Algebraic Number Fields, Manuscript, 1982.
  • [A] A. K. Lenstra, Factoring polynomials over algebraic number fields, Computer algebra (London, 1983) Lecture Notes in Comput. Sci., vol. 162, Springer, Berlin, 1983, pp. 245–254. MR 774816, 10.1007/3-540-12868-9_108
  • [A] K. Lenstra, Factoring Multivariate Polynomials Over Finite Fields, Proc. 15th ACM Sympos. Theory of Computing, Boston, 1983, pp. 189-192.
  • [A] A. K. Lenstra, Factoring multivariate integral polynomials, Automata, languages and programming (Barcelona, 1983) Lecture Notes in Comput. Sci., vol. 154, Springer, Berlin, 1983, pp. 458–465. MR 727676, 10.1007/BFb0036929
  • [A] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, 10.1007/BF01457454
  • [M] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 0354624, 10.1090/S0025-5718-1974-0354624-3
  • [A] M. Miola, "The conversion of Hensel codes to their rational equivalents," SIGSAM Bull., v. 16, 1982, pp. 24-26.
  • [D] David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 0396470
  • [A] Alexander Ostrowski, Über einige Lösungen der Funktionalgleichung 𝜓(𝑥)⋅𝜓(𝑥)=𝜓(𝑥𝑦), Acta Math. 41 (1916), no. 1, 271–284 (German). MR 1555153, 10.1007/BF02422947
  • [M] M. Sieveking, An algorithm for division of powerseries, Computing (Arch. Elektron. Rechnen) 10 (1972), 153–156 (English, with German summary). MR 0312701
  • [H] F. Trotter, Algebraic Numbers and Polynomial Factorization, Lecture Notes for AMS short course, Ann Arbor, August 1980.
  • [B] L. van der Waerden, Modern Algebra, Vol. 1, Ungar, New York, 1970.
  • [P] Paul S. Wang, An improved multivariate polynomial factoring algorithm, Math. Comp. 32 (1978), no. 144, 1215–1231. MR 0568284, 10.1090/S0025-5718-1978-0568284-3
  • [D] David Y. Y. Yun, Hensel meets Newton–algebraic constructions in an analytic complexity, Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975) Academic Press, New York, 1976, pp. 205–215. MR 0431775
  • [H] Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 0242793
  • [R] Zippel, Newton's Iteration and the Sparse Hensel Algorithm, Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation, Utah, 1981, pp. 68-72.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12J20, 65P05

Retrieve articles in all journals with MSC: 12J20, 65P05

Additional Information

Keywords: Valuation, factorization of polynomials, short vector algorithm, Hensel's method, Newton's method, partial differential equations
Article copyright: © Copyright 1984 American Mathematical Society