Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
Published electronically: November 30, 2012
MathSciNet review: 3042585
Full-text PDF

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.

References [Enhancements On Off] (What's this?)

  • [AGR95] C. Alonso, J. Gutierrez, and T. Recio.
    A rational function decomposition algorithm by near-separated polynomials.
    J. Symbolic Comput., 19(6):527-544, 1995. MR 1370620 (96j:13025)
  • [AT85] V. S. Alagar and Mai Thanh.
    Fast polynomial decomposition algorithms.
    In EUROCAL '85, Vol. 2 (Linz, 1985), volume 204 of Lecture Notes in Comput. Sci., pages 150-153. Springer, Berlin, 1985. MR 826564
  • [BCN] L. Busé, G. Chèze, and S. Najib.
    Noether's forms for the study of non-composite rational functions and their spectrum.
    A. Arithmetica, 147 (3): 217-231, 2011. MR 2773201
  • [BDN09] A. Bodin, P. Dèbes, and S. Najib.
    Indecomposable polynomials and their spectrum.
    A. Arithmetica, 139(1):79-100, 2009. MR 2538746 (2010j:12001)
  • [BHKS09] K. Belabas, M. van Hoeij, J. Klüners, and A. Steel.
    Factoring polynomials over global fields.
    J. Theorie des Nombres de Bordeaux, 21:15-39, 2009. MR 2537701 (2010d:12001)
  • [BL10] J. Berthomieu and G. Lecerf.
    Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations.
    Math. Comp. 81:1799-1821. DOI: MR 2904603
  • [BLS$ ^{+}$04] A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt.
    Complexity Issues in Bivariate Polynomial Factorization.
    In Proceedings of ISSAC 2004, pages 42-49. ACM, 2004. MR 2126923 (2005k:68084)
  • [BP94] D. Bini and V.Y. Pan.
    Polynomial and matrix computations. Vol. 1.
    Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1994.
    Fundamental algorithms. MR 1289412 (95k:65003)
  • [BZ85] D.R. Barton and R. Zippel.
    Polynomial decomposition algorithms.
    J. Symbolic Comput., 1(2):159-168, 1985. MR 818876 (87b:12001)
  • [Chè10] G. Chèze.
    Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Luroth's theorem.
    J. Complexity, 26(4):344-363, 2010. MR 2669662 (2011g:12006)
  • [Chè11] G. Chèze.
    Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time.
    J. Complexity, 27 (2): 246-262, 2011. MR 2776495
  • [CL07] G. Chèze and G. Lecerf.
    Lifting and recombination techniques for absolute factorization.
    J. Complexity, 23(3):380-420, 2007. MR 2330992 (2008f:68174)
  • [CN10] G. Chèze and S. Najib.
    Indecomposability of polynomials via Jacobian matrix.
    J. Algebra, 324(1):1-11, 2010. MR 2646027 (2011h:12003)
  • [Dic87] M. Dickerson.
    Polynomial decomposition algorithms for multivariate polynomials.
    Technical Report TR87-826, Comput. Sci., Cornell Univ., 1987.
  • [DLA06] F. Dumortier, J. Llibre, and J.C. Artés.
    Qualitative theory of planar differential systems.
    Universitext. Springer-Verlag, Berlin, 2006. MR 2256001 (2007f:34001)
  • [FGP10] J.-C. Faugère, J. von zur Gathen, and L. Perret.
    Decomposition of generic multivariate polynomials.
    In Proceedings of ISSAC 2010, pages 131-137. ACM, 2010. MR 2920546
  • [FP09] J.-C. Faugère and L. Perret.
    An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography.
    J. Symbolic Comput., 44(12):1676-1689, 2009. MR 2553573 (2010k:94036)
  • [Gat90a] J. von zur Gathen.
    Functional decomposition of polynomials: the tame case.
    J. Symbolic Comput., 9(3):281-299, 1990. MR 1056628 (92a:12015)
  • [Gat90b] J. von zur Gathen.
    Functional decomposition of polynomials: the wild case.
    J. Symbolic Comput., 10(5):437-452, 1990. MR 1087714 (92i:12008)
  • [Gat11] J. von zur Gathen.
    Counting decomposable multivariate polynomials.
    Appl. Algebra Eng. Commun. Comput. 22(3): 165-185, 2011. MR 2803912
  • [GG03] J. von zur Gathen and J. Gerhard.
    Modern computer algebra.
    Cambridge University Press, Cambridge, second edition, 2003. MR 2001757 (2004g:68202)
  • [GGR03] J. von zur Gathen, J. Gutierrez, and R. Rubio.
    Multivariate polynomial decomposition.
    Appl. Algebra Engrg. Comm. Comput., 14(1):11-31, 2003. MR 1989633 (2004i:12013)
  • [Gie88] M. Giesbrecht.
    Some results on the functional decomposition of polynomials.
    Master Thesis, University of Toronto, arXiv:1004.5433, 1988.
  • [GRS01] J. Gutierrez, R. Rubio, and D. Sevilla.
    Unirational fields of transcendence degree one and functional decomposition.
    In ISSAC '01: Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, pages 167-174, New York, NY, USA, 2001. ACM Press. MR 2049745 (2005g:12005)
  • [GW95] J. von zur Gathen and J. Weiss.
    Homogeneous bivariate decompositions.
    J. Symbolic Comput., 19(5):409-434, 1995. MR 1348781 (96f:12009)
  • [KL89] D. Kozen and S. Landau.
    Polynomial decomposition algorithms.
    J. Symbolic Comput., 7(5):445-456, 1989. MR 999513 (91c:13022)
  • [Klü99] J. Klüners.
    On polynomial decompositions.
    J. Symbolic Comput., 27(3):261-269, 1999. MR 1673595 (2000h:12004)
  • [Lec06] G. Lecerf.
    Sharp precision in Hensel lifting for bivariate polynomial factorization.
    Math. Comp., 75(254):921-933 (electronic), 2006. MR 2197000 (2007g:12008)
  • [Lec07] G. Lecerf.
    Improved dense multivariate polynomial factorization algorithms.
    J. Symbolic Comput., 42(4):477-494, 2007. MR 2317560 (2008e:13031)
  • [MO04] J. Moulin Ollagnier.
    Algebraic closure of a rational function.
    Qual. Theory Dyn. Syst., 5(2):285-300, 2004. MR 2275442 (2007h:13035)
  • [PI07] A.P. Petravchuk and O.G. Iena.
    On closed rational functions in several variables.
    Algebra Discrete Math., (2):115-124, 2007. MR 2364068 (2009a:26012)
  • [Rit22] J.F. Ritt.
    Prime and composite polynomials.
    Trans. Amer. Math. Soc., 23(1):51-66, 1922. MR 1501189
  • [Sch00] A. Schinzel.
    Polynomials with special regard to reducibility, volume 77 of Encyclopedia of Mathematics and its Applications.
    Cambridge University Press, Cambridge, 2000.
    With an appendix by Umberto Zannier. MR 1770638 (2001h:11135)
  • [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] M. Weimann.
    A lifting and recombination algorithm for rational factorization of sparse polynomials.
    J. Complexity, 26(6):608-628, 2010. MR 2735422 (2011j:12008)
  • [Zip91] R. Zippel.
    Rational function decomposition.
    In Proceedings of the 1991 international symposium on Symbolic and algebraic computation, pages 1-6. ACM Press, 1991.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 68W30, 12Y05, 12D05, 13P05

Retrieve articles in all journals with MSC (2010): 11Y16, 68W30, 12Y05, 12D05, 13P05

Additional Information

Guillaume Chèze
Affiliation: Institut de Mathématiques de Toulouse, Université Paul Sabatier Toulouse 3, MIP Bât 1R3, 31 062 TOULOUSE cedex 9, France

Received by editor(s): November 3, 2010
Received by editor(s) in revised form: November 22, 2011
Published electronically: November 30, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society