Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 [Enhancements On Off] (What's this?)

  • [AGL04] F. Abu Salem, S. Gao, and A. G. B. Lauder,
    Factoring polynomials via polytopes,
    In ISSAC '04: Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, pages 4-11, New York, 2004, ACM. MR 2126918 (2006a:13040)
  • [AKS07] M. Avendaño, T. Krick, and M. Sombra,
    Factoring bivariate sparse (lacunary) polynomials,
    J. Complexity, 23(2):193 - 216, 2007. MR 2314756 (2008i:11147)
  • [BCS97] P. Bürgisser, M. Clausen, and M. A. Shokrollahi,
    Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences],
    Springer-Verlag, Berlin, 1997. MR 1440179 (99c:68002)
  • [Ber97] L. Bernardin,
    On square-free factorization of multivariate polynomials over a finite field,
    Theoret. Comput. Sci., 187(1-2):105-116, 1997. MR 1479977 (98g:11137)
  • [Ber98] -,
    On bivariate Hensel lifting and its parallelization,
    In ISSAC '98: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, pages 96-100, New York, 1998, ACM. MR 1805171
  • [BHKS09] K. Belabas, M. van Hoeij, J. Klüners, and A. Steel,
    Factoring polynomials over global fields,
    J. Théor. Nombres Bordeaux, 21(1):15-39, 2009. MR 2537701 (2010d:12001)
  • [BLS+04] A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt,
    Complexity issues in bivariate polynomial factorization,
    In ISSAC '04: Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, pages 42-49, New York, 2004, ACM. MR 2126923 (2005k:68084)
  • [Chè10] G. Chèze,
    A recombination algorithm for the decomposition of multivariate rational functions,
    Manuscript available from
    hal-00531601/, 2010.
  • [Cox69] H. S. M. Coxeter,
    Introduction to Geometry,
    John Wiley & Sons Inc., New York, second edition, 1969. MR 0346644 (49:11369)
  • [Gao03] S. Gao,
    Factoring multivariate polynomials via partial differential equations,
    Math. Comp., 72:801-822, 2003. MR 1954969 (2003m:12014)
  • [Gat83] 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.
  • [GG03] J. von zur Gathen and J. Gerhard,
    Modern computer algebra,
    Cambridge University Press, second edition, 2003. MR 2001757 (2004g:68202)
  • [GK85] J. von zur Gathen and E. Kaltofen,
    Factoring sparse multivariate polynomials,
    J. Comput. System Sci., 31(2):265-287, 1985,
    Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828524 (87f:12002b)
  • [GR03] S. Gao and V. M. Rodrigues,
    Irreducibility of polynomials modulo $ p$ via Newton polytopes,
    J. Number Theory, 101(1):32-47, 2003. MR 1979651 (2004c:13043)
  • [GS93] B. Grünbaum and G. C. Shephard,
    Pick's theorem,
    Amer. Math. Monthly, 100(2):150-161, 1993. MR 1212401 (94j:52012)
  • [HL10] J. van der Hoeven and G. Lecerf,
    On the bit-complexity of sparse polynomial and series multiplication,
    Manuscript available from
    hal-00476223/, 2010.
  • [Kal85] E. Kaltofen,
    Sparse Hensel lifting,
    In EUROCAL '85, Vol. 2 (Linz, 1985), volume 204 of Lecture Notes in Comput. Sci., pages 4-17, Springer-Verlag, 1985. MR 826553 (88b:12001)
  • [Kal89] -,
    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.
  • [KK06] E. Kaltofen and P. Koiran,
    Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields,
    In ISSAC '06: Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, pages 162-168, New York, 2006, ACM. MR 2289115
  • [Lec06] G. Lecerf,
    Sharp precision in Hensel lifting for bivariate polynomial factorization,
    Math. Comp., 75:921-933, 2006. MR 2197000 (2007g:12008)
  • [Lec07] -,
    Improved dense multivariate polynomial factorization algorithms,
    J. Symbolic Comput., 42(4):477-494, 2007. MR 2317560 (2008e:13031)
  • [Lec08] -,
    Fast separable factorization and applications,
    Appl. Algebr. Engrg. Comm. Comput., 19(2), 2008.
  • [Lec10] -,
    New recombination algorithms for bivariate polynomial factorization based on Hensel lifting,
    Appl. Algebr. Engrg. Comm. Comput., 21(2):151-176, 2010. MR 2600710
  • [Ost21] 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.
  • [Ost75] -,
    On multiplication and factorization of polynomials, I. Lexicographic orderings and extreme aggregates of terms,
    Aequationes Math., 13(3):201-228, 1975. MR 0399060 (53:2911)
  • [Ost99] -,
    On the significance of the theory of convex polyhedra for formal algebra,
    SIGSAM Bull., 33(1):5, 1999,
    Translated from [Ost21].
  • [Pot08] 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
  • [PR10] A. Poteaux and M. Rybowicz,
    Complexity bounds for the rational Newton-Puiseux algorithm over finite fields,
    Appl. Algebra Engrg. Comm. Comput., 22(3):187-217, 2011. MR 2803913
  • [PS85] F. P. Preparata and M. I. Shamos,
    Computational Geometry: An Introduction,
    Springer-Verlag, 1985. MR 805539 (87d:68102)
  • [Ser73] J.-P. Serre,
    A Course in Arithmetic,
    Springer-Verlag, New York, 1973,
    Translated from the French, Graduate Texts in Mathematics, No. 7. MR 0344216 (49:8956)
  • [Ste05] A. Steel,
    Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic,
    J. Symbolic Comput., 40(3):1053-1075, 2005. MR 2167699 (2006f:13023)
  • [Wei10] M. Weimann,
    A lifting and recombination algorithm for rational factorization of sparse polynomials,
    J. Complexity, 26(6):608-628, 2010. MR 2735422
  • [Zip79] R. Zippel,
    Probabilistic algorithms for sparse polynomials,
    In EUROSAM '79: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 216-226, Springer-Verlag, 1979. MR 575692 (81g:68061)
  • [Zip81] 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.
  • [Zip93] -,
    Effective Polynomial Computation,
    Kluwer Academic Publishers, 1993.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 68W30, 11Y16, 12D05, 13P05

Retrieve articles in all journals with MSC (2010): 12Y05, 68W30, 11Y16, 12D05, 13P05

Additional Information

Jérémy Berthomieu
Affiliation: Laboratoire d’Informatique UMR 7161 CNRS, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France
Address at time of publication: Laboratoire de Mathématiques UMR8100 CNRS, Université de Versailles-Sr-Quentin-en-Yvelynes, 45 avenue des États-Unis, 78035 Versailles Cedex, France

Grégoire Lecerf
Affiliation: Laboratoire d’Informatique UMR 7161 CNRS, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France

Keywords: Polynomial factorization
Received by editor(s): October 15, 2010
Received by editor(s) in revised form: March 28, 2011, and April 11, 2011
Published electronically: November 10, 2011
Additional Notes: This work was partly supported by the French ANR-09-JCJC-0098-01 MaGiX project, and by the Digiteo 2009-36HD grant of the Région Île-de-France.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society