Hensel and Newton methods in valuation rings
HTML articles powered by AMS MathViewer
- by Joachim von zur Gathen PDF
- Math. Comp. 42 (1984), 637-661 Request permission
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
- E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x 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. Mach. 18 (1971), 478–504. MR 307450, DOI 10.1145/321662.321664
- 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
- George E. Collins, Subresultants and reduced polynomial remainder sequences, J. Assoc. Comput. Mach. 14 (1967), 128–142. MR 215512, DOI 10.1145/321371.321381 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. 11 (1958), 333–418. MR 100718, DOI 10.1002/cpa.3160110306
- A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London Ser. A 248 (1956), 407–432. MR 74349, DOI 10.1098/rsta.1956.0003 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 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, DOI 10.1007/BFb0036913
- 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
- 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, DOI 10.1137/0214035
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341–348. MR 351045, DOI 10.1007/BF01436917 Landau, Factoring Polynomials Over Algebraic Number Fields, Manuscript, 1982.
- A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-8 K. Lenstra, Factoring Multivariate Polynomials Over Finite Fields, Proc. 15th ACM Sympos. Theory of Computing, Boston, 1983, pp. 189-192.
- 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, DOI 10.1007/BFb0036929
- 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, DOI 10.1007/BF01457454
- M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 354624, DOI 10.1090/S0025-5718-1974-0354624-3 M. Miola, "The conversion of Hensel codes to their rational equivalents," SIGSAM Bull., v. 16, 1982, pp. 24-26.
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890
- Alexander Ostrowski, Über einige Lösungen der Funktionalgleichung $\psi (x)\cdot \psi (x)=\psi (xy)$, Acta Math. 41 (1916), no. 1, 271–284 (German). MR 1555153, DOI 10.1007/BF02422947
- M. Sieveking, An algorithm for division of powerseries, Computing (Arch. Elektron. Rechnen) 10 (1972), 153–156 (English, with German summary). MR 312701, DOI 10.1007/bf02242389 F. Trotter, Algebraic Numbers and Polynomial Factorization, Lecture Notes for AMS short course, Ann Arbor, August 1980. L. van der Waerden, Modern Algebra, Vol. 1, Ungar, New York, 1970.
- Paul S. Wang, Factoring multivariate polynomials over algebraic number fields, Math. Comp. 30 (1976), no. 134, 324–336. MR 568283, DOI 10.1090/S0025-5718-1976-0568283-X
- 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
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X Zippel, Newton’s Iteration and the Sparse Hensel Algorithm, Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation, Utah, 1981, pp. 68-72.
Additional Information
- © Copyright 1984 American Mathematical Society
- 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