Computer Science – Symbolic Computation
Scientific paper
2010-04-29
Journal of Complexity 26, 4 (2010) 344-363
Computer Science
Symbolic Computation
Scientific paper
10.1016/j.jco.2010.05.001
The extended L\"uroth's Theorem says that if the transcendence degree of $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)/\KK$ is 1 then there exists $f \in \KK(\underline{X})$ such that $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)$ is equal to $\KK(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.
No associations
LandOfFree
Nearly Optimal Algorithms for the Decomposition of Multivariate Rational Functions and the Extended Lüroth's Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Nearly Optimal Algorithms for the Decomposition of Multivariate Rational Functions and the Extended Lüroth's Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nearly Optimal Algorithms for the Decomposition of Multivariate Rational Functions and the Extended Lüroth's Theorem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-285151