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.

[AGL04] 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, https://doi.org/10.1145/1005285.1005289
[AKS07] 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, https://doi.org/10.1016/j.jco.2006.06.002
[BCS97] 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
[Ber97] 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, https://doi.org/10.1016/S0304-3975(97)00059-5
[Ber98] 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, https://doi.org/10.1145/281508.281567
[BHKS09] 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
[BLS+04] 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, https://doi.org/10.1145/1005285.1005294
[Chè10] G. Chèze,
A recombination algorithm for the decomposition of multivariate rational functions,
Manuscript available from http://hal.archives-ouvertes.fr/
hal-00531601/, 2010.
[Cox69] H. S. M. Coxeter, Introduction to geometry, 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR 0346644
[Gao03] Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Math. Comp. 72 (2003), no. 242, 801–822. MR 1954969, https://doi.org/10.1090/S0025-5718-02-01428-X
[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] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
[GK85] Joachim von zur Gathen, Irreducibility of multivariate polynomials, J. Comput. System Sci. 31 (1985), no. 2, 225–264. Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828523, https://doi.org/10.1016/0022-0000(85)90043-1
[GR03] Shuhong Gao and Virgínia M. Rodrigues, Irreducibility of polynomials modulo 𝑝 via Newton polytopes, J. Number Theory 101 (2003), no. 1, 32–47. MR 1979651, https://doi.org/10.1016/S0022-314X(03)00044-1
[GS93] Branko Grünbaum and G. C. Shephard, Pick’s theorem, Amer. Math. Monthly 100 (1993), no. 2, 150–161. MR 1212401, https://doi.org/10.2307/2323771
[HL10] 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.
[Kal85] 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, https://doi.org/10.1007/3-540-15984-3_230
[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] 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, https://doi.org/10.1145/1145768.1145798
[Lec06] Grégoire Lecerf, Sharp precision in Hensel lifting for bivariate polynomial factorization, Math. Comp. 75 (2006), no. 254, 921–933. MR 2197000, https://doi.org/10.1090/S0025-5718-06-01810-2
[Lec07] Grégoire Lecerf, Improved dense multivariate polynomial factorization algorithms, J. Symbolic Comput. 42 (2007), no. 4, 477–494. MR 2317560, https://doi.org/10.1016/j.jsc.2007.01.003
[Lec08] -,
Fast separable factorization and applications,
Appl. Algebr. Engrg. Comm. Comput., 19(2), 2008.
[Lec10] 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, https://doi.org/10.1007/s00200-010-0121-5
[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] 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, https://doi.org/10.1007/BF01836524
[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 http://www-salsa.lip6.fr/~poteaux/.
[PR10] 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, https://doi.org/10.1007/s00200-011-0144-6
[PS85] Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539
[Ser73] 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
[Ste05] 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, https://doi.org/10.1016/j.jsc.2005.03.002
[Wei10] Martin Weimann, A lifting and recombination algorithm for rational factorization of sparse polynomials, J. Complexity 26 (2010), no. 6, 608–628. MR 2735422, https://doi.org/10.1016/j.jco.2010.06.005
[Zip79] 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
[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.

Visit our AMS Resources & Updates page