Algoritmo de Buchberger

En geometría algebraica computacional y álgebra conmutativa computacional, el algoritmo de Buchberger es un método para transformar un conjunto dado de generadores de un ideal de polinomios en una base de Gröbner con respecto a algún orden monomial. Fue inventado por el matemático austríaco Bruno Buchberger.^[1]​ Se puede ver como una generalización del algoritmo euclidiano para calcular el máximo común divisor y de la eliminación Gaussiana para sistemas lineales.

Algoritmo

A continuación se muestra una versión tosca de este algoritmo para encontrar una base para un ideal I de un anillo de polinomios R:

Entrada: Un conjunto de polinomios finito F que genera I

Salida: Una base de Gröbner G para I

1. G := F
2. Para cada f_i, f_j en G, se denota por g_i al término líder de f_i con respecto del orden dado, y por a_ij al mínimo común múltiplo de g_i y g_j.
3. Se escogen dos polinomios en G, y se denota S_ij = (a_ij / g_i) f_i − (a_ij / g_j) f_j (Obsérvese que los términos líderes se cancelan por construcción).
4. Se reduce Sij, mediante el algoritmo de división multivariante, con respecto del conjunto G hasta que el resultado no se pueda reducir más. Si el resultado es distinto de cero, se añade a G.
5. Se repiten los pasos 2-4 hasta que todos los pares posibles hayan sido considerados, incluidos los que contienen polinomios añadidos en el paso 4.
6. Se devuelve G.

Al polinomio Sij se le suele denominar el S-polinomio, donde S se refiere a sustracción (Buchberger) o sizigia (otros). El par de polinomios con que está asociado es comúnmente llamado par crítico.

Hay numerosas maneras de mejorar el algoritmo. Por ejemplo, se puede reducir cada nuevo elemento de G con respecto de los demás antes de añadirlos. Si los términos líderes de f_i y f_j no tienen variables en común, entonces S_ij siempre se reducirá a 0 (si solo se usan f_i y f_j en la reducción), luego no es necesario calcularlo todo.

El algoritmo termina porque el ideal monomial generado por los términos líderes del conjunto F aumenta en cada iteración, y el Lema de Dickson (o el Teorema de la base de Hilbert) garantiza que cualquier cadena ascendente de este tipo se estabiliza (se acaba volviendo constante).

Complejidad

La complejidad computacional del algoritmo de Buchberger es muy difícil de estimar, debido a la cantidad de elecciones que pueden cambiar drásticamente el tiempo de cálculo. No obstante, TW Dubé ha demostrado^[2]​ que los grados de los elementos de una base de Gröbner reducida siempre están acotados por

${\displaystyle 2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}}$,

donde n es el número de variables y d es el grado total máximo de los polinomios de entrada. Esto permite, en teoría, utilizar álgebra lineal sobre el espacio vectorial de los polinomios de grado como mucho este valor, para obtener un algoritmo de complejidad ${\displaystyle d^{2^{n+o(1)}}}$ .

Por otro lado, hay ejemplos^[3]​ donde la base de Gröbner contiene elementos de grado

${\displaystyle d^{2^{\Omega (n)}}}$,

y el límite superior de complejidad anterior es óptimo. Sin embargo, estos ejemplos son extremadamente raros.

Desde su descubrimiento, se han introducido muchas variantes de Buchberger para mejorar su eficiencia. Los algoritmos F4 y F5 de Faugère son actualmente los algoritmos más eficientes para calcular bases de Gröbner y permiten calcular de forma rutinaria bases de Gröbner que constan de cientos de polinomios, cada uno de los cuales con cientos de términos, a su vez con coeficientes de cientos de dígitos.

Véase también

• Algoritmo de Quine–McCluskey – algoritmo análogo en álgebra booleana

Referencias

1. Multidimensional systems theory Web del instituto RISC
2. Dubé, Thomas W. (1990). «The Structure of Polynomial Ideals and Gröbner Bases». SIAM Journal on Computing 19 (4): 750. doi:10.1137/0219053. 
3. Mayr, Ernst W; Meyer, Albert R (1982). «The complexity of the word problems for commutative semigroups and polynomial ideals». Advances in Mathematics 46 (3): 305. doi:10.1016/0001-8708(82)90048-2. 

Leer más

• Buchberger, B. (August 1976). «Theoretical Basis for the Reduction of Polynomials to Canonical Forms». ACM SIGSAM Bulletin (ACM) 10 (3): 19-29. doi:10.1145/1088216.1088219. 
• David Cox, John Little, and Donald O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. ISBN 0-387-94680-2.
• Vladimir P. Gerdt, Yuri A. Blinkov (1998). Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation, 45:519ff

Enlaces externos

• Hazewinkel, Michiel, ed. (2001), «Algoritmo de Buchberger», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .
• Buchberger's algorithm en Scholarpedia
• Weisstein, Eric W. «Buchberger's Algorithm». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.