Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Luroth Theorem

作者：Cheze Guillaume^*

来源：Journal of Complexity, 2010, 26(4): 344-363.

DOI：10.1016/j.jco.2010.05.001

• Algorithm
• Complexity
• Decomposition
• Luroth's Theorem
• Factorization

The extended Luroth Theorem says that if the transcendence degree of K(f(1),..., f(m))/K is 1 then there exists f is an element of K((X) under bar) such that K(f(1),..., f(m)) is equal to K(f). In this paper we show how to compute f with a probabilistic algorithm. We also describe a probabilistic and a deterministic algorithm for the decomposition of multivariate rational functions. The probabilistic algorithms proposed in this paper are softly optimal when n is fixed and d tends to infinity. We also give an indecomposability test based on gcd computations and Newton's polytope. In the last section, we show that we get a polynomial time algorithm, with a minor modification in the exponential time decomposition algorithm proposed by Gutierez-Rubio-Sevilla in 2001.

• 出版日期2010-8