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
HTML articles powered by AMS MathViewer

by Guillaume Chèze;

Math. Comp. 82 (2013), 1793-1812

DOI: https://doi.org/10.1090/S0025-5718-2012-02658-5

Published electronically: November 30, 2012

PDF | Request permission

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.

References

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, DOI 10.1006/jsco.1995.1030
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, DOI 10.1007/3-540-15984-3_{2}49
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, DOI 10.4064/aa147-3-2
Arnaud Bodin, Pierre Dèbes, and Salah Najib, Indecomposable polynomials and their spectrum, Acta Arith. 139 (2009), no. 1, 79–100. MR 2538746, DOI 10.4064/aa139-1-7
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
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, DOI 10.1090/S0025-5718-2011-02562-7
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 10.1145/1005285.1005294
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, DOI 10.1007/978-1-4612-0265-3
David R. Barton and Richard Zippel, Polynomial decomposition algorithms, J. Symbolic Comput. 1 (1985), no. 2, 159–168. MR 818876, DOI 10.1016/S0747-7171(85)80012-2
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, DOI 10.1016/j.jco.2010.05.001
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, DOI 10.1016/j.jco.2010.10.004
Guillaume Chèze and Grégoire Lecerf, Lifting and recombination techniques for absolute factorization, J. Complexity 23 (2007), no. 3, 380–420. MR 2330992, DOI 10.1016/j.jco.2007.01.008
G. Chèze and S. Najib, Indecomposability of polynomials via Jacobian matrix, J. Algebra 324 (2010), no. 1, 1–11. MR 2646027, DOI 10.1016/j.jalgebra.2010.01.007
M. Dickerson. Polynomial decomposition algorithms for multivariate polynomials. Technical Report TR87-826, Comput. Sci., Cornell Univ., 1987.
Freddy Dumortier, Jaume Llibre, and Joan C. Artés, Qualitative theory of planar differential systems, Universitext, Springer-Verlag, Berlin, 2006. MR 2256001
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, DOI 10.1145/1837934.1837963
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, DOI 10.1016/j.jsc.2008.02.005
Joachim von zur Gathen, Functional decomposition of polynomials: the tame case, J. Symbolic Comput. 9 (1990), no. 3, 281–299. MR 1056628, DOI 10.1016/S0747-7171(08)80014-4
Joachim von zur Gathen, Functional decomposition of polynomials: the wild case, J. Symbolic Comput. 10 (1990), no. 5, 437–452. MR 1087714, DOI 10.1016/S0747-7171(08)80054-5
Joachim von zur Gathen, Counting decomposable multivariate polynomials, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 3, 165–185. MR 2803912, DOI 10.1007/s00200-011-0141-9
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
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, DOI 10.1007/s00200-003-0122-8
M. Giesbrecht. Some results on the functional decomposition of polynomials. Master Thesis, University of Toronto, arXiv:1004.5433, 1988.
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, DOI 10.1145/384101.384124
Joachim von zur Gathen and Jürgen Weiss, Homogeneous bivariate decompositions, J. Symbolic Comput. 19 (1995), no. 5, 409–434. MR 1348781, DOI 10.1006/jsco.1995.1024
Dexter Kozen and Susan Landau, Polynomial decomposition algorithms, J. Symbolic Comput. 7 (1989), no. 5, 445–456. MR 999513, DOI 10.1016/S0747-7171(89)80027-6
Jürgen Klüners, On polynomial decompositions, J. Symbolic Comput. 27 (1999), no. 3, 261–269. MR 1673595, DOI 10.1006/jsco.1998.0252
Grégoire Lecerf, Sharp precision in Hensel lifting for bivariate polynomial factorization, Math. Comp. 75 (2006), no. 254, 921–933. MR 2197000, DOI 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 10.1016/j.jsc.2007.01.003
Jean Moulin Ollagnier, Algebraic closure of a rational function, Qual. Theory Dyn. Syst. 5 (2004), no. 2, 285–300. MR 2275442, DOI 10.1007/BF02972683
Anatoliy P. Petravchuk and Oleksandr G. Iena, On closed rational functions in several variables, Algebra Discrete Math. 2 (2007), 115–124. MR 2364068
J. F. Ritt, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922), no. 1, 51–66. MR 1501189, DOI 10.1090/S0002-9947-1922-1501189-9
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, DOI 10.1017/CBO9780511542916
A. Storjohann. Algorithms for matrix canonical forms. PhD thesis, ETH Zurich, Zurich, Switzerland, 2000.
S. Watt. Functional decomposition of symbolic polynomials. In International Conference on Computatioanl Sciences and its Applications, pages 353–362. IEEE Computer Society, 2008.
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.
Martin Weimann, A lifting and recombination algorithm for rational factorization of sparse polynomials, J. Complexity 26 (2010), no. 6, 608–628. MR 2735422, DOI 10.1016/j.jco.2010.06.005
R. Zippel. Rational function decomposition. In Proceedings of the 1991 international symposium on Symbolic and algebraic computation, pages 1–6. ACM Press, 1991.