A recombination algorithm for the decomposition of multivariate rational functions

Chèze, Guillaume

doi:10.1090/S0025-5718-2012-02658-5

A recombination algorithm for the decomposition of multivariate rational functions

Author: Guillaume Chèze
Journal: Math. Comp. 82 (2013), 1793-1812
MSC (2010): Primary 11Y16, 68W30; Secondary 12Y05, 12D05, 13P05
DOI: https://doi.org/10.1090/S0025-5718-2012-02658-5
Published electronically: November 30, 2012
MathSciNet review: 3042585
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we show how we can compute in a deterministic way the decomposition of a multivariate rational function with a recombination strategy. The key point of our recombination strategy is the use of Darboux polynomials. We study the complexity of this strategy and we show that this method improves the previous ones. In the appendix, we explain how the strategy proposed recently by J. Berthomieu and G. Lecerf for the sparse factorization can be used in the decomposition setting. Then we deduce a decomposition algorithm in the sparse bivariate case and we give its complexity.

[AGR95] Cesar Alonso, Jaime Gutierrez, and Tomas Recio, A rational function decomposition algorithm by near-separated polynomials, J. Symbolic Comput. 19 (1995), no. 6, 527–544. MR 1370620, https://doi.org/10.1006/jsco.1995.1030
[AT85] V. S. Alagar and Mai Thanh, Fast polynomial decomposition algorithms, EUROCAL ’85, Vol. 2 (Linz, 1985) Lecture Notes in Comput. Sci., vol. 204, Springer, Berlin, 1985, pp. 150–153. MR 826564, https://doi.org/10.1007/3-540-15984-3_249
[BCN] Laurent Busé, Guillaume Chèze, and Salah Najib, Noether forms for the study of non-composite rational functions and their spectrum, Acta Arith. 147 (2011), no. 3, 217–231. MR 2773201, https://doi.org/10.4064/aa147-3-2
[BDN09] Arnaud Bodin, Pierre Dèbes, and Salah Najib, Indecomposable polynomials and their spectrum, Acta Arith. 139 (2009), no. 1, 79–100. MR 2538746, https://doi.org/10.4064/aa139-1-7
[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
[BL10] Jérémy Berthomieu and Grégoire Lecerf, Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations, Math. Comp. 81 (2012), no. 279, 1799–1821. MR 2904603, https://doi.org/10.1090/S0025-5718-2011-02562-7
[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
[BP94] Dario Bini and Victor Y. Pan, Polynomial and matrix computations. Vol. 1, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1994. Fundamental algorithms. MR 1289412
[BZ85] David R. Barton and Richard Zippel, Polynomial decomposition algorithms, J. Symbolic Comput. 1 (1985), no. 2, 159–168. MR 818876, https://doi.org/10.1016/S0747-7171(85)80012-2
[Chè10] Guillaume Chèze, Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem, J. Complexity 26 (2010), no. 4, 344–363. MR 2669662, https://doi.org/10.1016/j.jco.2010.05.001
[Chè11] Guillaume Chèze, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, J. Complexity 27 (2011), no. 2, 246–262. MR 2776495, https://doi.org/10.1016/j.jco.2010.10.004
[CL07] Guillaume Chèze and Grégoire Lecerf, Lifting and recombination techniques for absolute factorization, J. Complexity 23 (2007), no. 3, 380–420. MR 2330992, https://doi.org/10.1016/j.jco.2007.01.008
[CN10] G. Chèze and S. Najib, Indecomposability of polynomials via Jacobian matrix, J. Algebra 324 (2010), no. 1, 1–11. MR 2646027, https://doi.org/10.1016/j.jalgebra.2010.01.007
[Dic87] M. Dickerson.
Polynomial decomposition algorithms for multivariate polynomials.
Technical Report TR87-826, Comput. Sci., Cornell Univ., 1987.
[DLA06] Freddy Dumortier, Jaume Llibre, and Joan C. Artés, Qualitative theory of planar differential systems, Universitext, Springer-Verlag, Berlin, 2006. MR 2256001
[FGP10] Jean-Charles Faugère, Joachim von zur Gathen, and Ludovic Perret, Decomposition of generic multivariate polynomials, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 131–137. MR 2920546, https://doi.org/10.1145/1837934.1837963
[FP09] Jean-Charles Faugère and Ludovic Perret, An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography, J. Symbolic Comput. 44 (2009), no. 12, 1676–1689. MR 2553573, https://doi.org/10.1016/j.jsc.2008.02.005
[Gat90a] Joachim von zur Gathen, Functional decomposition of polynomials: the tame case, J. Symbolic Comput. 9 (1990), no. 3, 281–299. MR 1056628, https://doi.org/10.1016/S0747-7171(08)80014-4
[Gat90b] Joachim von zur Gathen, Functional decomposition of polynomials: the wild case, J. Symbolic Comput. 10 (1990), no. 5, 437–452. MR 1087714, https://doi.org/10.1016/S0747-7171(08)80054-5
[Gat11] Joachim von zur Gathen, Counting decomposable multivariate polynomials, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 3, 165–185. MR 2803912, https://doi.org/10.1007/s00200-011-0141-9
[GG03] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
[GGR03] Joachim von zur Gathen, Jaime Gutierrez, and Rosario Rubio, Multivariate polynomial decomposition, Appl. Algebra Engrg. Comm. Comput. 14 (2003), no. 1, 11–31. MR 1989633, https://doi.org/10.1007/s00200-003-0122-8
[Gie88] M. Giesbrecht.
Some results on the functional decomposition of polynomials.
Master Thesis, University of Toronto, arXiv:1004.5433, 1988.
[GRS01] Jaime Gutierrez, Rosario Rubio, and David Sevilla, Unirational fields of transcendence degree one and functional decomposition, Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2001, pp. 167–174. MR 2049745, https://doi.org/10.1145/384101.384124
[GW95] Joachim von zur Gathen and Jürgen Weiss, Homogeneous bivariate decompositions, J. Symbolic Comput. 19 (1995), no. 5, 409–434. MR 1348781, https://doi.org/10.1006/jsco.1995.1024
[KL89] Dexter Kozen and Susan Landau, Polynomial decomposition algorithms, J. Symbolic Comput. 7 (1989), no. 5, 445–456. MR 999513, https://doi.org/10.1016/S0747-7171(89)80027-6
[Klü99] Jürgen Klüners, On polynomial decompositions, J. Symbolic Comput. 27 (1999), no. 3, 261–269. MR 1673595, https://doi.org/10.1006/jsco.1998.0252
[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
[MO04] Jean Moulin Ollagnier, Algebraic closure of a rational function, Qual. Theory Dyn. Syst. 5 (2004), no. 2, 285–300. MR 2275442, https://doi.org/10.1007/BF02972683
[PI07] Anatoliy P. Petravchuk and Oleksandr G. Iena, On closed rational functions in several variables, Algebra Discrete Math. 2 (2007), 115–124. MR 2364068
[Rit22] J. F. Ritt, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922), no. 1, 51–66. MR 1501189, https://doi.org/10.1090/S0002-9947-1922-1501189-9
[Sch00] A. Schinzel, Polynomials with special regard to reducibility, Encyclopedia of Mathematics and its Applications, vol. 77, Cambridge University Press, Cambridge, 2000. With an appendix by Umberto Zannier. MR 1770638
[Sto00] A. Storjohann.
Algorithms for matrix canonical forms.
PhD thesis, ETH Zurich, Zurich, Switzerland, 2000.
[Wat08] S. Watt.
Functional decomposition of symbolic polynomials.
In International Conference on Computatioanl Sciences and its Applications, pages 353-362. IEEE Computer Society, 2008.
[Wat09] S. Watt.
Algorithms for the functional decomposition of Laurent polynomials.
In Conferences on Intelligent Computer Mathematics 2009: 16th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning and 8th International Conference on Mathematical Knowledge Management, (Calculemus 2009), pages 186-200. Springer-Verlag LNAI 5625, 2009.
[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
[Zip91] R. Zippel.
Rational function decomposition.
In Proceedings of the 1991 international symposium on Symbolic and algebraic computation, pages 1-6. ACM Press, 1991.