Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem
type: Item
instance of: scholarly article
title: Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem
zbMATH Open document ID: 1216.65054
published in: Journal of Complexity
publication date: 2010-09-01T00:00:00Z
review text: Let \(f(X_1,\dots,X_n)=f_1(X_1,\dots,X_n)/f_2(X_1,\dots,X_n) \in \mathbb K(X_1,\dots,X_n)\) be a rational function, where \(\mathbb K\) is a field and \(n\geq 2\). It is said to be composite if it can be written as \(f=u\circ h\), where \(u \in \mathbb K(T)\) such that \(\deg(u)\geq 2\). \textit{J. Moulin-Ollagnier} [Qual. Theory Dyn. Syst. 5, No.~2, 285--300 (2004; Zbl 1121.13301)] has found a multivariate rational function decomposition algorithm which is not optimal and works only for fields of characteristic zero. The author of this paper introduces a probablilistic optimal algorithm that decomposes \(f \in \mathbb K(X_1,\dots,X_n)\) using \(\widetilde{\mathcal O}(d^n)\) arithmetic operations, where \(d=\deg(f)\). Finally, the author shows how to modify the Gutieres-Rubio-Sevilla decomposition algorithm in order to obtain a polynomial time algorithm instead of an exponential time algorithm.
Mathematics Subject Classification ID: 65H04
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 13P05
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5777313
zbMATH Keywords: Lüroth's theorem
zbMATH Keywords: rational functions
zbMATH Keywords: factorization
zbMATH Keywords: complexity
zbMATH Keywords: Gutieres-Rubio-Sevilla decomposition algorithm
zbMATH Keywords: polynomial time algorithm
author: Guillaume Chèze
reviewed by: Przemysław Stpiczyński
MaRDI profile type: Publication
full work available at URL: j.jco.2010.05.001
OpenAlex ID: W3103289733
cites work: Translates of Polynomials
cites work: A rational function decomposition algorithm by near-separated polynomials
cites work: Polynomial decomposition algorithms
cites work: Q4314299
cites work: Reducibility of rational functions in several variables
cites work: Fast Algorithms for Manipulating Formal Power Series
cites work: A matrix-based approach to properness and inversion problems for rational surfaces
cites work: Lifting and recombination techniques for absolute factorization
cites work: Q3031075
cites work: Irreducibility of polynomials modulo \(p\) via Newton polytopes.
cites work: Unirational fields of transcendence degree one and functional decomposition
cites work: Building counterexamples to generalizations for rational functions of Ritt's decomposition theorem
cites work: On a Theorem of Lueroth
cites work: Equations de Pfaff algébriques
cites work: Fast parallel absolute irreducibility testing
cites work: Sharp precision in Hensel lifting for bivariate polynomial factorization
cites work: Improved dense multivariate polynomial factorization algorithms
cites work: Reducibility of polynomials in two variables
cites work: Recognizing simple subextensions of purely transcendental field extensions
cites work: Algebraic closure of a rational function
cites work: Reduzibilität ebener Kurven.
cites work: A note on a theorem of Fried and MacRae
cites work: Reducibility of polynomials in several variables. II
cites work: Q4488096
cites work: Improperly parametrized rational curves
cites work: Q3963106
cites work: Q3784166
cites work: The number of reducible hypersurfaces in a pencil. -- Erratum
cites work: Functional decomposition of polynomials: the tame case
cites work: Functional decomposition of polynomials: the wild case
cites work: Q4406533
cites work: Multivariate polynomial decomposition
cites work: Q4237364
DOI: 10.1016/J.JCO.2010.05.001
description: scientific article; zbMATH DE number 5777313