Algoritmo de Buchberger
# 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. 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
   * G := F

   * 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.$

   * 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).

   * 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.

   * 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.

   * 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 que los grados de los elementos de una base de Gröbner reducida siempre están acotados por

    $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 $d^{2^{n+o(1)}}$ .

Por otro lado, hay ejemplos donde la base de Gröbner contiene elementos de grado

    $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.

