A recombination algorithm for the decomposition of multivariate rational functions

DOI10.1090/S0025-5718-2012-02658-5MaRDI QIDQ2840631zbMATH OpenOpenAlexFDO

Authors Guillaume Chèze

Publication date 23 July 2013

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.0972

Mathematics Subject Classification ID

Polynomials in real and complex fields: factorization (12D05) Symbolic computation and algebraic computation (68W30)

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 used of Darboux polynomials. We study the complexity of this strategy and we show that this method improves the previous ones. In 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

Recommendations

• On multivariate rational function decomposition
• Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem
• A rational function decomposition algorithm by near-separated polynomials
• Decomposition of algebraic functions
• scientific article; zbMATH DE number 1091158

Cites work

• A lifting and recombination algorithm for rational factorization of sparse polynomials
• A rational function decomposition algorithm by near-separated polynomials
• Algebraic closure of a rational function
• Algorithms for the Functional Decomposition of Laurent Polynomials
• An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography
• Complexity issues in bivariate polynomial factorization
• Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time
• Counting decomposable multivariate polynomials
• Decomposition of generic multivariate polynomials
• Factoring polynomials over global fields
• Functional decomposition of polynomials: the tame case
• Functional decomposition of polynomials: the wild case
• Homogeneous bivariate decompositions
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1467743 (Why is no real title available?)
• Improved dense multivariate polynomial factorization algorithms
• Indecomposability of polynomials via Jacobian matrix
• Indecomposable polynomials and their spectrum
• Lifting and recombination techniques for absolute factorization
• Multivariate polynomial decomposition
• Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem
• Noether forms for the study of non-composite rational functions and their spectrum
• On closed rational functions in several variables
• On polynomial decompositions
• Polynomial decomposition algorithms
• Polynomial decomposition algorithms
• Qualitative theory of planar differential systems
• Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
• Sharp precision in Hensel lifting for bivariate polynomial factorization
• Unirational fields of transcendence degree one and functional decomposition

Cited in

(2)

• Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields
• On multivariate rational function decomposition

This page was built for publication: A recombination algorithm for the decomposition of multivariate rational functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840631)