Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations

Berthomieu, Jérémy; Lecerf, Grégoire

doi:10.1090/S0025-5718-2011-02562-7

Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
HTML articles powered by AMS MathViewer

by Jérémy Berthomieu and Grégoire Lecerf PDF

Math. Comp. 81 (2012), 1799-1821 Request permission

Abstract:

In this article we present a new algorithm for reducing the usual sparse bivariate factorization problems to the dense case. This reduction simply consists of computing an invertible monomial transformation that produces a polynomial with a dense size of the same order of magnitude as the size of the integral convex hull of the support of the input polynomial. This approach turns out to be very efficient in practice, as demonstrated with our implementation.

References

Fatima Abu Salem, Shuhong Gao, and Alan G. B. Lauder, Factoring polynomials via polytopes, ISSAC 2004, ACM, New York, 2004, pp. 4–11. MR 2126918, DOI 10.1145/1005285.1005289
Martín Avendaño, Teresa Krick, and Martín Sombra, Factoring bivariate sparse (lacunary) polynomials, J. Complexity 23 (2007), no. 2, 193–216. MR 2314756, DOI 10.1016/j.jco.2006.06.002
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
Laurent Bernardin, On square-free factorization of multivariate polynomials over a finite field, Theoret. Comput. Sci. 187 (1997), no. 1-2, 105–116. Computer algebra (Saint-Louis, 1996). MR 1479977, DOI 10.1016/S0304-3975(97)00059-5
Laurent Bernardin, On bivariate Hensel lifting and its parallelization, Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (Rostock), ACM, New York, 1998, pp. 96–100. MR 1805171, DOI 10.1145/281508.281567
Karim Belabas, Mark van Hoeij, Jürgen Klüners, and Allan Steel, Factoring polynomials over global fields, J. Théor. Nombres Bordeaux 21 (2009), no. 1, 15–39 (English, with English and French summaries). MR 2537701
A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt, Complexity issues in bivariate polynomial factorization, ISSAC 2004, ACM, New York, 2004, pp. 42–49. MR 2126923, DOI 10.1145/1005285.1005294
G. Chèze, A recombination algorithm for the decomposition of multivariate rational functions, Manuscript available from http://hal.archives-ouvertes.fr/ hal-00531601/, 2010.
H. S. M. Coxeter, Introduction to geometry, 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR 0346644
Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Math. Comp. 72 (2003), no. 242, 801–822. MR 1954969, DOI 10.1090/S0025-5718-02-01428-X
J. von zur Gathen, Factoring sparse multivariate polynomials, In 24th Annual IEEE Symposium on Foundations of Computer Science, pages 172–179, Los Alamitos, CA, USA, 1983, IEEE Computer Society.
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
Joachim von zur Gathen and Erich Kaltofen, Factoring sparse multivariate polynomials, J. Comput. System Sci. 31 (1985), no. 2, 265–287. Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828524, DOI 10.1016/0022-0000(85)90044-3
Shuhong Gao and Virgínia M. Rodrigues, Irreducibility of polynomials modulo $p$ via Newton polytopes, J. Number Theory 101 (2003), no. 1, 32–47. MR 1979651, DOI 10.1016/S0022-314X(03)00044-1
Branko Grünbaum and G. C. Shephard, Pick’s theorem, Amer. Math. Monthly 100 (1993), no. 2, 150–161. MR 1212401, DOI 10.2307/2323771
J. van der Hoeven and G. Lecerf, On the bit-complexity of sparse polynomial and series multiplication, Manuscript available from http://hal.archives-ouvertes.fr/ hal-00476223/, 2010.
Erich Kaltofen, Sparse Hensel lifting, EUROCAL ’85, Vol. 2 (Linz, 1985) Lecture Notes in Comput. Sci., vol. 204, Springer, Berlin, 1985, pp. 4–17. MR 826553, DOI 10.1007/3-540-15984-3_{2}30
—, Factorization of polynomials given by straight-line programs, In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 375–412, JAI, 1989.
Erich Kaltofen and Pascal Koiran, Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields, ISSAC 2006, ACM, New York, 2006, pp. 162–168. MR 2289115, DOI 10.1145/1145768.1145798
Grégoire Lecerf, Sharp precision in Hensel lifting for bivariate polynomial factorization, Math. Comp. 75 (2006), no. 254, 921–933. MR 2197000, DOI 10.1090/S0025-5718-06-01810-2
Grégoire Lecerf, Improved dense multivariate polynomial factorization algorithms, J. Symbolic Comput. 42 (2007), no. 4, 477–494. MR 2317560, DOI 10.1016/j.jsc.2007.01.003
—, Fast separable factorization and applications, Appl. Algebr. Engrg. Comm. Comput., 19(2), 2008.
Grégoire Lecerf, New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, Appl. Algebra Engrg. Comm. Comput. 21 (2010), no. 2, 151–176. MR 2600710, DOI 10.1007/s00200-010-0121-5
A. M. Ostrowski, Über die Bedeutung der Theorie der konvexen Polyeder für die formale Algebra, Jahresber. Deutsch. Math.-Verein., 30(2):98–99, 1921, Talk given at Der Deutsche Mathematikertag vom 18–24 September 1921 in Jena.
A. M. Ostrowski, On multiplication and factorization of polynomials. I. Lexicographic orderings and extreme aggregates of terms, Aequationes Math. 13 (1975), no. 3, 201–228. MR 399060, DOI 10.1007/BF01836524
—, On the significance of the theory of convex polyhedra for formal algebra, SIGSAM Bull., 33(1):5, 1999, Translated from [Ost21].
A. Poteaux, Calcul de développements de Puiseux et application au calcul du groupe de monodromie d’une courbe algébrique plane, PhD thesis, Université de Limoges, 2008, Manuscript available from http://www-salsa.lip6.fr/~poteaux/.
Adrien Poteaux and Marc Rybowicz, Complexity bounds for the rational Newton-Puiseux algorithm over finite fields, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 3, 187–217. MR 2803913, DOI 10.1007/s00200-011-0144-6
Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539, DOI 10.1007/978-1-4612-1098-6
J.-P. Serre, A course in arithmetic, Graduate Texts in Mathematics, No. 7, Springer-Verlag, New York-Heidelberg, 1973. Translated from the French. MR 0344216
Allan Steel, Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic, J. Symbolic Comput. 40 (2005), no. 3, 1053–1075. MR 2167699, DOI 10.1016/j.jsc.2005.03.002
Martin Weimann, A lifting and recombination algorithm for rational factorization of sparse polynomials, J. Complexity 26 (2010), no. 6, 608–628. MR 2735422, DOI 10.1016/j.jco.2010.06.005
Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR 575692
R. Zippel, Newton’s iteration and the sparse Hensel algorithm (Extended Abstract), In SYMSAC ’81: Proceedings of the fourth ACM Symposium on Symbolic and Algebraic Computation, pages 68–72, New York, 1981, ACM.
—, Effective Polynomial Computation, Kluwer Academic Publishers, 1993.