|
Cálculo del Máximo Común Divisor de
dos Polinomios en |
| El problema de calcular el máximo común divisor (MCD) de
dos polinomios es de importancia fundamental en álgebra
computacional. Estos cálculos aparecen como subproblemas en
operaciones aritméticas sobre funciones racionales o
aparecen como cálculo prominente en factorización de
polinomios y en integración simbólica, además de otros
cálculos en álgebra. En general, podemos calcular el MCD de dos polinomios usando una variación del algoritmo de Euclides. El algoritmo de Euclides es conocido desde mucho tiempo atrás, es fácil de entender y de implementar. Sin embargo, desde el punto de vista del álgebra computacional, este algoritmo tiene varios inconvenientes. Desde finales de los sesentas se han desarrollado algoritmos mejorados usando técnicas un poco más sofisticadas. En esta primera parte vamos a entrar en la teoría básica y en los algoritmos (relativamente) más sencillos, el algoritmo "subresultant PRS'' (aquí lo llamaremos PRS subresultante) y el algoritmo heurístico (conocido como "GCDHEU''). Este último algoritmo es muy eficiente en problemas de pocas variables y se usa también como complemento de otros algoritmos. De hecho, se estima que el 90% de los cálculos de MCD's en MAPLE se hacen con este algoritmo [13]. No se puede decir con certeza que haya un "mejor'' algoritmo para el cálculo del MCD de dos polinomios. Los algoritmos más usados, para calcular MCD en  son "EZ-GCD'' (Extended
Zassenhaus GCD), GCDHEU y "SPMOD'' (Sparse
Modular Algorithm) [16]GCDHEU es más veloz que EZGCD y SPMOD en algunos casos, especialmente para polinomios con cuatro o menos variables. En general, SPMOD es más veloz que EZGCD y GCDHEU en problemas donde los polinomios son "ralos'', es decir con muchos coeficientes nulos y éstos, en la práctica, son la mayoría. En la segunda parte, en el próximo número, nos dedicaremos a EZGCD y SPMOD. Estos algoritmos requieren técnicas más sofisticadas basadas en inversión de homomorfismos vía el teorema chino del resto, iteración lineal p-ádica de Newton y construcción de Hensel. Como CGDHEU es un algoritmo modular, aprovechamos para iniciar con parte de la teoría necesaria para los dos primeros algoritmos. En este trabajo, primero vamos a presentar los preliminares algebraicos, el algoritmo de Euclides, el algoritmo primitivo de Euclides, el algoritmo PRS Subresultante y el algoritmo heurístico, además de el algoritmo extendido de Euclides. Las implementaciones requieren, por simplicidad, construir un par de clases para manejo de polinomios con coeficientes racionales grandes ("BigRational'') y para manejo de polinomios con coeficientes enteros grandes ("BigInteger'').
|
| > |
Cidse -
Revista virtual Matemática, Educación e Internet -
ITCR
Derechos Reservados