×

A recombination algorithm for the decomposition of multivariate rational functions. (English) Zbl 1336.12002

Summary: 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 [Math. Comput. 81, No. 279, 1799–1821 (2012; Zbl 1271.12006)] 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.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
12D05 Polynomials in real and complex fields: factorization

Citations:

Zbl 1271.12006
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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. · Zbl 0840.68048
[2] 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.
[3] 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. · Zbl 1235.12005
[4] Arnaud Bodin, Pierre Dèbes, and Salah Najib, Indecomposable polynomials and their spectrum, Acta Arith. 139 (2009), no. 1, 79 – 100. · Zbl 1228.12002
[5] 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). · Zbl 1254.11116
[6] 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. · Zbl 1271.12006
[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. · Zbl 1134.68595
[8] 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. · Zbl 0809.65012
[9] David R. Barton and Richard Zippel, Polynomial decomposition algorithms, J. Symbolic Comput. 1 (1985), no. 2, 159 – 168. · Zbl 0605.12012
[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. · Zbl 1216.65054
[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. · Zbl 1215.65040
[12] Guillaume Chèze and Grégoire Lecerf, Lifting and recombination techniques for absolute factorization, J. Complexity 23 (2007), no. 3, 380 – 420. · Zbl 1130.12007
[13] G. Chèze and S. Najib, Indecomposability of polynomials via Jacobian matrix, J. Algebra 324 (2010), no. 1, 1 – 11. · Zbl 1202.13014
[14] M. Dickerson. Polynomial decomposition algorithms for multivariate polynomials. Technical Report TR87-826, Comput. Sci., Cornell Univ., 1987.
[15] Freddy Dumortier, Jaume Llibre, and Joan C. Artés, Qualitative theory of planar differential systems, Universitext, Springer-Verlag, Berlin, 2006. · Zbl 1110.34002
[16] 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. · Zbl 1321.68530
[17] 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. · Zbl 1175.12004
[18] Joachim von zur Gathen, Functional decomposition of polynomials: the tame case, J. Symbolic Comput. 9 (1990), no. 3, 281 – 299. · Zbl 0716.68053
[19] Joachim von zur Gathen, Functional decomposition of polynomials: the wild case, J. Symbolic Comput. 10 (1990), no. 5, 437 – 452. · Zbl 0722.12003
[20] Joachim von zur Gathen, Counting decomposable multivariate polynomials, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 3, 165 – 185. · Zbl 1288.68298
[21] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. · Zbl 1055.68168
[22] Joachim von zur Gathen, Jaime Gutierrez, and Rosario Rubio, Multivariate polynomial decomposition, Appl. Algebra Engrg. Comm. Comput. 14 (2003), no. 1, 11 – 31. · Zbl 1103.12004
[23] M. Giesbrecht. Some results on the functional decomposition of polynomials. Master Thesis, University of Toronto, arXiv:1004.5433, 1988.
[24] 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. · Zbl 1356.12003
[25] Joachim von zur Gathen and Jürgen Weiss, Homogeneous bivariate decompositions, J. Symbolic Comput. 19 (1995), no. 5, 409 – 434. · Zbl 0967.12006
[26] Dexter Kozen and Susan Landau, Polynomial decomposition algorithms, J. Symbolic Comput. 7 (1989), no. 5, 445 – 456. · Zbl 0691.68030
[27] Jürgen Klüners, On polynomial decompositions, J. Symbolic Comput. 27 (1999), no. 3, 261 – 269. · Zbl 0967.12002
[28] Grégoire Lecerf, Sharp precision in Hensel lifting for bivariate polynomial factorization, Math. Comp. 75 (2006), no. 254, 921 – 933. · Zbl 1125.12003
[29] Grégoire Lecerf, Improved dense multivariate polynomial factorization algorithms, J. Symbolic Comput. 42 (2007), no. 4, 477 – 494. · Zbl 1127.13021
[30] Jean Moulin Ollagnier, Algebraic closure of a rational function, Qual. Theory Dyn. Syst. 5 (2004), no. 2, 285 – 300. · Zbl 1121.13301
[31] Anatoliy P. Petravchuk and Oleksandr G. Iena, On closed rational functions in several variables, Algebra Discrete Math. 2 (2007), 115 – 124. · Zbl 1164.26329
[32] J. F. Ritt, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922), no. 1, 51 – 66. · JFM 48.0079.01
[33] 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. · Zbl 0956.12001
[34] A. Storjohann. Algorithms for matrix canonical forms. PhD thesis, ETH Zurich, Zurich, Switzerland, 2000.
[35] S. Watt. Functional decomposition of symbolic polynomials. In International Conference on Computatioanl Sciences and its Applications, pages 353-362. IEEE Computer Society, 2008.
[36] 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. · Zbl 1247.68329
[37] Martin Weimann, A lifting and recombination algorithm for rational factorization of sparse polynomials, J. Complexity 26 (2010), no. 6, 608 – 628. · Zbl 1236.12001
[38] R. Zippel. Rational function decomposition. In Proceedings of the 1991 international symposium on Symbolic and algebraic computation, pages 1-6. ACM Press, 1991.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.