Hensel and Newton methods in valuation rings

Author:
Joachim von zur Gathen

Journal:
Math. Comp. **42** (1984), 637-661

MSC:
Primary 12J20; Secondary 65P05

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736459-9

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.

**[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 ,"*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.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736459-9

Keywords:
Valuation,
factorization of polynomials,
short vector algorithm,
Hensel's method,
Newton's method,
partial differential equations

Article copyright:
© Copyright 1984
American Mathematical Society