A rational function decomposition algorithm by near-separated polynomials.

Alonso, César, Gutiérrez, Jaime, and Recio, Tomás. "Un algoritmo de descomposición de funciones racionales mediante polinomios casi-separados.." Extracta Mathematicae 11.3 (1996): 475-479. <http://eudml.org/doc/38498>.

@article{Alonso1996,
abstract = {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.},
author = {Alonso, César, Gutiérrez, Jaime, Recio, Tomás},
journal = {Extracta Mathematicae},
keywords = {Algoritmos polinomiales; Función racional; Descomposición; decomposition; rational function; separated polynomial},
language = {spa},
number = {3},
pages = {475-479},
title = {Un algoritmo de descomposición de funciones racionales mediante polinomios casi-separados.},
url = {http://eudml.org/doc/38498},
volume = {11},
year = {1996},
}

TY - JOUR
AU - Alonso, César
AU - Gutiérrez, Jaime
AU - Recio, Tomás
TI - Un algoritmo de descomposición de funciones racionales mediante polinomios casi-separados.
JO - Extracta Mathematicae
PY - 1996
VL - 11
IS - 3
SP - 475
EP - 479
AB - 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.
LA - spa
KW - Algoritmos polinomiales; Función racional; Descomposición; decomposition; rational function; separated polynomial
UR - http://eudml.org/doc/38498
ER -