Un algoritmo de descomposición de funciones racionales mediante polinomios casi-separados.

Título inglés	A rational function decomposition algorithm by near-separated polynomials.
Título español	Un algoritmo de descomposición de funciones racionales mediante polinomios casi-separados.
Autor/es	Alonso, César ; Gutiérrez, Jaime ; Recio, Tomás
Organización	Dep. Mat. Univ. Oviedo, Oviedo, España;Dep. Mat. Estadist. Comput. Univ. Cantabria, Santander, España
Revista	0213-8743
Publicación	1996, 11 (3): 475-479, 11 Ref.
Tipo de documento	articulo
Idioma	Español
Resumen español	Dado un polinomio f perteneciente a K[x], determinar si existen otros dos g y h de grado mayor que uno tales que f(x) = g(h(x)) = g o h, y, en caso de que existan, encontrarlos, es conocido como problema de descomposición para polinomios. Cuando dicha descomposición existe, problemas como la evaluación de f en un punto o la resolución de la ecuación f = 0 se pueden resolver de manera más simple. La generalización del problema de la descomposición al caso de funciones racionales es sin duda un problema más difícil. La descomposición de funciones racionales ha sido estudiada ya en [10] y en [8]. Recientemente, en [11] se presenta el primer algoritmo en tiempo polinomial para la descomposición de funciones racionales. No obstante dicho algoritmo requiere en uno de sus pasos la factorización de un polinomio sobre un cuerpo de funciones algebraicas. El propio Zippel comenta acerca de su algoritmo, que sería muy difícil descomponer funciones racionales de grado superior a 10. Nosotros presentamos en esta breve nota un algoritmo para la descomposición de funciones racionales siguiendo la idea de Barton & Zippel en [4] para el caso de polinomios. Aunque nuestro algoritmo requiere en principio un número exponencial, en el grado de f, de operaciones en el cuerpo K, resulta en la práctica más eficiente que el de Zippel, pues se pueden descomponer funciones racionales de grado mucho mayor que la cota por él estimada.
Clasificación UNESCO	120101 ; 120501
Palabras clave español	Algoritmos polinomiales ; Función racional ; Descomposición
Código MathReviews	MR1456545
Código Z-Math	Zbl 0959.12005
Acceso al artículo completo