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.
- 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.
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
Email:
berthomieu@lix.polytechnique.fr
Grégoire Lecerf
Affiliation:
Laboratoire d’Informatique UMR 7161 CNRS, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France
Email:
gregoire.lecerf@math.cnrs.fr
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.