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

Authors: Jérémy Berthomieu and Grégoire Lecerf
Journal: Math. Comp. 81 (2012), 1799-1821
MSC (2010): Primary ~12Y05; Secondary ~68W30, 11Y16, 12D05, 13P05
DOI: https://doi.org/10.1090/S0025-5718-2011-02562-7
Published electronically: November 10, 2011
MathSciNet review: 2904603
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 https://doi.org/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 https://doi.org/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
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 https://doi.org/10.1016/S0304-3975%2897%2900059-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0022-0000%2885%2990044-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 https://doi.org/10.1016/S0022-314X%2803%2900044-1

Branko Grünbaum and G. C. Shephard, Pick’s theorem, Amer. Math. Monthly 100 (1993), no. 2, 150–161. MR 1212401, DOI https://doi.org/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 https://doi.org/10.1007/3-540-15984-3_230

---, 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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

J.-P. Serre, A course in arithmetic, Springer-Verlag, New York-Heidelberg, 1973. Translated from the French; Graduate Texts in Mathematics, No. 7. 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 https://doi.org/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 https://doi.org/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.