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

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] R. Berlekamp, "Factoring polynomials over finite fields," Bell System Tech. J., v. 46, 1967, pp. 1853-1859. MR 0219231 (36:2314)
  • [N] Bourbaki, Eléments de Mathématiques, Livre II: Algèbre, Hermann, Paris, 1958.
  • [W] S. Brown, "On Euclid's algorithm and the computation of polynomial greatest common divisors," J. Assoc. Comput. Math., v. 18, 1971, pp. 478-504. MR 0307450 (46:6570)
  • [A] L. Chistov & D. Yu. Grigoryev, Polynomial-Time Factoring of the Multivariable Polynomials Over a Global Field, LOMI preprint E-5-82, Leningrad, 1982. MR 1082380 (92f:12018)
  • [G] E. Collins, "Subresultants and reduced polynomial remainder sequences," J. Assoc. Comput. Mach., v. 14, 1967, pp. 128-142. MR 0215512 (35:6352)
  • [A] Fellmann, Newton-Iteration über nicht-archimedisch bewerteten vollständigen Ringen, Diplomarbeit, Zürich, 1977.
  • [K] O. Friedrichs, "Symmetric positive linear differential equations," Comm. Pure Appl. Math., v. 9, 1958, pp. 333-418. MR 0100718 (20:7147)
  • [A] Fröhlich & J. C. Shepherdson, "Effective procedures in field theory," Philos. Trans. Roy. Soc. London Ser. A, v. 248, 1955-56, pp. 407-432. MR 0074349 (17:570d)
  • [J] von zur Gathen, Factoring Sparse Multivariate Polynomials, Proc. 24th Annual IEEE Sympos. Foundations of Computer Science, Tucson, 1983, pp. 172-179.
  • [J] von zur Gathen & E. Kaltofen, Polynomial-Time Factorization of Multivariate Polynomials Over Finite Fields, Proc. 10th ICALP, Barcelona, 1983, pp. 250-263. MR 727661 (85d:11104)
  • [E] Kaltofen, A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization, Proc. 23rd Annual IEEE Sympos. Foundations of Computer Science, Chicago, 1982, pp. 57-64. MR 780381
  • [E] Kaltofen, "Polynomial-time reduction from multivariate to bivariate and univariate integer polynomial factorization," SIAM J. Comput. (To appear.) MR 784750 (86j:12001)
  • [D] E. Knuth, The Art of Computer Programming, Vol. 2, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [H] T. Kung, "On computing reciprocals of power series," Numer. Math., v. 22, 1974, pp. 341-348. MR 0351045 (50:3536)
  • [S] Landau, Factoring Polynomials Over Algebraic Number Fields, Manuscript, 1982.
  • [A] K. Lenstra, Factoring Polynomials Over Algebraic Number Fields, Preprint, Mathematisch Centrum, Amsterdam, 1982. MR 774816 (86g:12001b)
  • [A] K. Lenstra, Factoring Multivariate Polynomials Over Finite Fields, Proc. 15th ACM Sympos. Theory of Computing, Boston, 1983, pp. 189-192.
  • [A] K. Lenstra [83a], Factoring Multivariate Integral Polynomials, Proc. 10th ICALP, Barcelona, 1983, pp. 458-465. MR 727676 (85f:12001)
  • [A] K. Lenstra, H. W. Lenstra & L. Lovász, "Factoring polynomials with rational coefficients," Math. Ann., v. 261, 1982, pp. 515-534. MR 682664 (84a:12002)
  • [M] Mignotte, "An inequality about factors of polynomials," Math. Comp., v. 28, 1974, pp. 1153-1157. MR 0354624 (50:7102)
  • [A] M. Miola, "The conversion of Hensel codes to their rational equivalents," SIGSAM Bull., v. 16, 1982, pp. 24-26.
  • [D] R. Musser, "Multivariate polynomial factorization," J. Assoc. Comput. Mach., v. 22, 1975, pp. 291-308. MR 0396470 (53:335a)
  • [A] Ostrowski, "Ueber einige Lösungen der Funktionalgleichung $ \varphi (x) \bullet \varphi (y) = \varphi (xy)$," Acta Math., v. 41, 1918, pp. 271-284. MR 1555153
  • [M] Sieveking, "An algorithm for division of powerseries," Computing, v. 10, 1972, pp. 153-156. MR 0312701 (47:1257)
  • [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] S. Wang, "An improved multivariate polynomial factoring algorithm," Math. Comp., v. 32, 1978, pp. 1215-1231. MR 0568284 (58:27887b)
  • [D] Y. Y. Yun, "Hensel meets Newton--Algebraic constructions in an analytic setting," In Analytic Computational Complexity (J. F. Traub, ed.), Academic Press, New York, 1976. MR 0431775 (55:4770)
  • [H] Zassenhaus, "On Hensel factorization. I," J. Number Theory, v. 1, 1969, pp. 291-311. MR 0242793 (39:4120)
  • [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

American Mathematical Society